{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Calculator LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: calculate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #计算器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。</p>\n",
    "\n",
    "<p>表达式仅包含非负整数，<code>+</code>， <code>-</code> ，<code>*</code>，<code>/</code> 四种运算符和空格&nbsp;<code>&nbsp;</code>。 整数除法仅保留整数部分。</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong>&quot;3+2*2&quot;\n",
    "<strong>输出:</strong> 7\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> &quot; 3/2 &quot;\n",
    "<strong>输出:</strong> 1</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> &quot; 3+5 / 2 &quot;\n",
    "<strong>输出:</strong> 5\n",
    "</pre>\n",
    "\n",
    "<p><strong>说明：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你可以假设所给定的表达式都是有效的。</li>\n",
    "\t<li>请<strong>不要</strong>使用内置的库函数 <code>eval</code>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [calculator-lcci](https://leetcode.cn/problems/calculator-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [calculator-lcci](https://leetcode.cn/problems/calculator-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def calculate(num1,num2):\n",
    "            return set([num1*num2,num1/num2 if num2 != 0 else 0,num2/num1 if num1 != 0 else 0,num1-num2,num2-num1,num1+num2])\n",
    "        #cards = [8,1,6,6]\n",
    "        for i in range(1,4):\n",
    "            rest = [j for j in range(1,4) if j != i]\n",
    "            set1 = calculate(cards[0], cards[i])\n",
    "            set2 = calculate(cards[rest[0]], cards[rest[1]])\n",
    "            for num1 in set1:\n",
    "                for num2 in set2:\n",
    "                    for num in calculate(num1, num2):\n",
    "                        if (num - 24)**2 <= 0.001:\n",
    "                            #print(i)\n",
    "                            return True\n",
    "        for i in range(4):\n",
    "            for j in range(4):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                rest = [k for k in range(4) if (k != i and k != j)]\n",
    "                for num2 in calculate(cards[rest[0]], cards[rest[1]]):\n",
    "                    for num1 in calculate(cards[j], num2):\n",
    "                        for num in calculate(cards[i], num1):\n",
    "                            if (num - 24)**2 <= 0.001:\n",
    "                                # print(cards[i],num1)\n",
    "                                # print(calculate(cards[i], num1))\n",
    "                                # print(cards[j], num2)\n",
    "                                # print(calculate(cards[j], num2))\n",
    "                                # print(cards[rest[0]], cards[rest[1]])\n",
    "                                # print(calculate(cards[rest[0]], cards[rest[1]]))\n",
    "                                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def calculate(num1,num2):\n",
    "            return set([num1*num2,num1/num2 if num2 != 0 else 0,num2/num1 if num1 != 0 else 0,num1-num2,num2-num1,num1+num2])\n",
    "        #cards = [8,1,6,6]\n",
    "        for i in range(1,4):\n",
    "            rest = [j for j in range(1,4) if j != i]\n",
    "            set1 = calculate(cards[0], cards[i])\n",
    "            set2 = calculate(cards[rest[0]], cards[rest[1]])\n",
    "            for num1 in set1:\n",
    "                for num2 in set2:\n",
    "                    for num in calculate(num1, num2):\n",
    "                        if (abs(num) - 24)**2 <= 0.001:\n",
    "                            #print(i)\n",
    "                            return True\n",
    "        for i in range(4):\n",
    "            for j in range(4):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                rest = [k for k in range(4) if (k != i and k != j)]\n",
    "                for num2 in calculate(cards[rest[0]], cards[rest[1]]):\n",
    "                    for num1 in calculate(cards[j], num2):\n",
    "                        for num in calculate(cards[i], num1):\n",
    "                            if (abs(num) - 24)**2 <= 0.001:\n",
    "                                # print(cards[i],num1)\n",
    "                                # print(calculate(cards[i], num1))\n",
    "                                # print(cards[j], num2)\n",
    "                                # print(calculate(cards[j], num2))\n",
    "                                # print(cards[rest[0]], cards[rest[1]])\n",
    "                                # print(calculate(cards[rest[0]], cards[rest[1]]))\n",
    "                                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        MIN_OFFSET = 10**(-6)\n",
    "        def calculate(a,b):\n",
    "            possible_number = [a+b,a-b, a*b]\n",
    "            if abs(a)>MIN_OFFSET:possible_number.append(b/a)\n",
    "            if abs(b)>MIN_OFFSET:possible_number.append(a/b)\n",
    "            return set(possible_number)\n",
    "\n",
    "        for i in range(4):\n",
    "            a= cards[i]\n",
    "            for j in range(4):\n",
    "                b =cards[j]\n",
    "                if i==j:continue\n",
    "\n",
    "                for cur_c in calculate(*[cards[k] for k in range(4) if (k not in [i,j])]):\n",
    "                    # (ab)c\n",
    "                    for cur_a in  calculate(a,b):\n",
    "                        for result in calculate(cur_a, cur_c):\n",
    "                            if abs(result-24)<MIN_OFFSET:\n",
    "                                return True\n",
    "                    # a(bc)\n",
    "                    for cur_b in calculate(b,cur_c):\n",
    "                        for result in calculate(a, cur_b):\n",
    "                            if abs(result-24)<MIN_OFFSET:\n",
    "                                return True\n",
    "        return False\n",
    "\n",
    "                \n",
    "\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #运算符列表\n",
    "    operator=['+','-','*','/']\n",
    "\n",
    "    #运算顺序\n",
    "    # cal_strs=[]\n",
    "\n",
    "    def calculate(self,arr:list[int],k):\n",
    "        length=len(arr)\n",
    "\n",
    "        #只有一个数则判断其是否等于k\n",
    "        if length==1:\n",
    "            return abs(arr[0]-k)<1e-6\n",
    "        \n",
    "        #遍历所有可用操作符\n",
    "        for op in self.operator:\n",
    "            #遍历运算符前后的两个数的排列组合\n",
    "            for i in range(0,length):\n",
    "                start=0 if op in ('/','-') else i+1\n",
    "                for j in range(start,length):\n",
    "\n",
    "                    #约束条件 两个数不可相同 第一个操作数必须大于第二个操作数\n",
    "                    # if j==i or arr[i]<arr[j]:\n",
    "                    if j==i :\n",
    "                        continue\n",
    "            \n",
    "                    #约束条件 如果op为除号且不能整除 则抛弃\n",
    "                    # if op=='/' and (arr[j]==0 or arr[i]%arr[j]!=0):\n",
    "                    if op=='/' and (arr[j]==0):\n",
    "                        continue\n",
    "                    \n",
    "                    #计算该次计算的值\n",
    "                    if op=='+':\n",
    "                        num=arr[i]+arr[j]\n",
    "                    elif op=='-':\n",
    "                        num=arr[i]-arr[j]\n",
    "                    elif op=='*':\n",
    "                        num=arr[i]*arr[j]\n",
    "                    else:\n",
    "                        num=arr[i]/arr[j]\n",
    "                    # num=eval(f\"{arr[i]}{op}{arr[j]}\")\n",
    "                    \n",
    "                    #生成新的数组 除去第i j个元素 加上num\n",
    "                    new_arr=[]\n",
    "                    for index,n in enumerate(arr):\n",
    "                        if index!=i and index!=j:\n",
    "                            new_arr.append(n)\n",
    "                    new_arr.append(num)\n",
    "        \n",
    "                    #使用新数组计算24点 如成功则返回成功\n",
    "                    if self.calculate(new_arr,k):\n",
    "                        # cal_strs.insert(0,f\"{arr[i]}{op}{arr[j]}={num}\")\n",
    "                        return True\n",
    "                \n",
    "        return False\n",
    "\n",
    "\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        :type cards: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.calculate(cards,24)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        def calculate(num1,num2):\n",
    "            return set([num1*num2,num1/num2 if num2 != 0 else 0,num2/num1 if num1 != 0 else 0,num1-num2,num1+num2])\n",
    "        #cards = [8,1,6,6]\n",
    "        for i in range(1,4):\n",
    "            rest = [j for j in range(1,4) if j != i]\n",
    "            set1 = calculate(cards[0], cards[i])\n",
    "            set2 = calculate(cards[rest[0]], cards[rest[1]])\n",
    "            for num1 in set1:\n",
    "                for num2 in set2:\n",
    "                    for num in calculate(num1, num2):\n",
    "                        if (abs(num) - 24)**2 <= 0.001:\n",
    "                            #print(i)\n",
    "                            return True\n",
    "        for i in range(4):\n",
    "            for j in range(4):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                rest = [k for k in range(4) if (k != i and k != j)]\n",
    "                for num2 in calculate(cards[rest[0]], cards[rest[1]]):\n",
    "                    for num1 in calculate(cards[j], num2):\n",
    "                        for num in calculate(cards[i], num1):\n",
    "                            if (abs(num) - 24)**2 <= 0.001:\n",
    "                                # print(cards[i],num1)\n",
    "                                # print(calculate(cards[i], num1))\n",
    "                                # print(cards[j], num2)\n",
    "                                # print(calculate(cards[j], num2))\n",
    "                                # print(cards[rest[0]], cards[rest[1]])\n",
    "                                # print(calculate(cards[rest[0]], cards[rest[1]]))\n",
    "                                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #运算符列表\n",
    "    operator=['+','-','*','/']\n",
    "\n",
    "    #运算顺序\n",
    "    # cal_strs=[]\n",
    "\n",
    "    def calculate(self,arr:list[int],k):\n",
    "        length=len(arr)\n",
    "\n",
    "        #只有一个数则判断其是否等于k\n",
    "        if length==1:\n",
    "            return abs(arr[0]-k)<1e-6\n",
    "        \n",
    "        #遍历所有可用操作符\n",
    "        for op in self.operator:\n",
    "            #遍历运算符前后的两个数的排列组合\n",
    "            for i in range(0,length):\n",
    "                start=0 if op in ('/','-') else i+1\n",
    "                for j in range(start,length):\n",
    "\n",
    "                    #约束条件 两个数不可相同 第一个操作数必须大于第二个操作数\n",
    "                    # if j==i or arr[i]<arr[j]:\n",
    "                    if j==i :\n",
    "                        continue\n",
    "            \n",
    "                    #约束条件 如果op为除号且不能整除 则抛弃\n",
    "                    # if op=='/' and (arr[j]==0 or arr[i]%arr[j]!=0):\n",
    "                    if op=='/' and (arr[j]==0):\n",
    "                        continue\n",
    "                    \n",
    "                    #计算该次计算的值\n",
    "                    if op=='+':\n",
    "                        num=arr[i]+arr[j]\n",
    "                    elif op=='-':\n",
    "                        num=arr[i]-arr[j]\n",
    "                    elif op=='*':\n",
    "                        num=arr[i]*arr[j]\n",
    "                    else:\n",
    "                        num=arr[i]/arr[j]\n",
    "                    # num=eval(f\"{arr[i]}{op}{arr[j]}\")\n",
    "                    \n",
    "                    #生成新的数组 除去第i j个元素 加上num\n",
    "                    new_arr=[]\n",
    "                    for index,n in enumerate(arr):\n",
    "                        if index!=i and index!=j:\n",
    "                            new_arr.append(n)\n",
    "                    new_arr.append(num)\n",
    "        \n",
    "                    #使用新数组计算24点 如成功则返回成功\n",
    "                    if self.calculate(new_arr,k):\n",
    "                        # cal_strs.insert(0,f\"{arr[i]}{op}{arr[j]}={num}\")\n",
    "                        return True\n",
    "                \n",
    "        return False\n",
    "\n",
    "\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        :type cards: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.calculate(cards,24)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #运算符列表\n",
    "    operator=['+','-','*','/']\n",
    "\n",
    "    #运算顺序\n",
    "    # cal_strs=[]\n",
    "\n",
    "    def calculate(self,arr:list[int],k):\n",
    "        length=len(arr)\n",
    "\n",
    "        #只有一个数则判断其是否等于k\n",
    "        if length==1:\n",
    "            return abs(arr[0]-k)<1e-6\n",
    "        \n",
    "        #遍历所有可用操作符\n",
    "        for op in self.operator:\n",
    "            #遍历运算符前后的两个数的排列组合\n",
    "            for i in range(0,length):\n",
    "                for j in range(0,length):\n",
    "\n",
    "                    #约束条件 两个数不可相同 第一个操作数必须大于第二个操作数\n",
    "                    # if j==i or arr[i]<arr[j]:\n",
    "                    if j==i :\n",
    "                        continue\n",
    "            \n",
    "                    #约束条件 如果op为除号且不能整除 则抛弃\n",
    "                    # if op=='/' and (arr[j]==0 or arr[i]%arr[j]!=0):\n",
    "                    if op=='/' and (arr[j]==0):\n",
    "                        continue\n",
    "                    \n",
    "                    #计算该次计算的值\n",
    "                    num=eval(f\"{arr[i]}{op}{arr[j]}\")\n",
    "                    \n",
    "                    #生成新的数组 除去第i j个元素 加上num\n",
    "                    new_arr=[]\n",
    "                    for index,n in enumerate(arr):\n",
    "                        if index!=i and index!=j:\n",
    "                            new_arr.append(n)\n",
    "                    new_arr.append(num)\n",
    "        \n",
    "                    #使用新数组计算24点 如成功则返回成功\n",
    "                    if self.calculate(new_arr,k):\n",
    "                        # cal_strs.insert(0,f\"{arr[i]}{op}{arr[j]}={num}\")\n",
    "                        return True\n",
    "                \n",
    "        return False\n",
    "\n",
    "\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        :type cards: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.calculate(cards,24)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        MIN_OFFSET = 10**(-6)\n",
    "        def calculate(a,b):\n",
    "            possible_number = [a+b,a-b, a*b]\n",
    "            if abs(a)>MIN_OFFSET:possible_number.append(b/a)\n",
    "            if abs(b)>MIN_OFFSET:possible_number.append(a/b)\n",
    "            return set(possible_number)\n",
    "\n",
    "\n",
    "        # number_set = set()\n",
    "        for i in range(4):\n",
    "            a= cards[i]\n",
    "            for j in range(4):\n",
    "                b =cards[j]\n",
    "                if i==j:continue\n",
    "                possible_set = calculate(*[cards[k] for k in range(4) if (k not in [i,j])])\n",
    "\n",
    "                for cur_c in possible_set:\n",
    "                    \n",
    "                    # (ab)c\n",
    "                    for new_a in  calculate(a,b):\n",
    "                        for cur_result in calculate(new_a, cur_c):\n",
    "                            if abs(cur_result-24)<MIN_OFFSET:\n",
    "                                return True\n",
    "\n",
    "                    for new_b in calculate(b,cur_c):\n",
    "                        for cur_result in calculate(a, new_b):\n",
    "                            if abs(cur_result-24)<MIN_OFFSET:\n",
    "                                return True\n",
    "        return False\n",
    "\n",
    "                \n",
    "\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumClosest(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        nums_len = len(nums)\n",
    "        ans, total_num = 99999999, 99999999\n",
    "        for i in range(nums_len):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            left = i + 1\n",
    "            right = nums_len - 1\n",
    "            while left < right:\n",
    "                total = nums[i] + nums[left] + nums[right]\n",
    "                diff = self.calculate_difference(target, total)\n",
    "                if diff == 0:\n",
    "                    return total\n",
    "                if ans > diff:\n",
    "                    ans = diff\n",
    "                    total_num = total\n",
    "                if total > target:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "\n",
    "        return total_num\n",
    "                \n",
    "    \n",
    "    def calculate_difference(self, num1: int, num2: int):\n",
    "        if num1 >= num2:\n",
    "            return num1 -num2\n",
    "        return num2 - num1\n",
    "\n",
    "\n",
    "# -10 -7 -2 0 4 8 12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        count = collections.Counter(arr)\n",
    "        keys = sorted(count)\n",
    "        \n",
    "        ans = 0\n",
    "        \n",
    "        # Now, let's do a 3sum on \"keys\", for i <= j <= k.\n",
    "        # We will use count to add the correct contribution to ans.\n",
    "        for i, x in enumerate(keys):\n",
    "            T = target - x\n",
    "            j, k = i, len(keys) - 1\n",
    "            while j <= k:\n",
    "                y, z = keys[j], keys[k]\n",
    "                if y + z < T:\n",
    "                    j += 1\n",
    "                elif y + z > T:\n",
    "                    k -= 1\n",
    "                else: # x+y+z == T, now calculate the size of the contribution\n",
    "                    if i < j < k:\n",
    "                        ans += count[x] * count[y] * count[z]\n",
    "                    elif i == j < k:\n",
    "                        ans += count[x] * (count[x] - 1) / 2 * count[z]\n",
    "                    elif i < j == k:\n",
    "                        ans += count[x] * count[y] * (count[y] - 1) / 2\n",
    "                    else:\n",
    "                        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6\n",
    "\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "                    \n",
    "        return int(ans % MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, A: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        count = collections.Counter(A)  # 频率\n",
    "        keys = sorted(count)  # key排序\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # Now, let's do a 3sum on \"keys\", for i <= j <= k.\n",
    "        # We will use count to add the correct contribution to ans.\n",
    "        for i, x in enumerate(keys):\n",
    "            T = target - x\n",
    "            j, k = i, len(keys) - 1\n",
    "            while j <= k:\n",
    "                y, z = keys[j], keys[k]\n",
    "                if y + z < T:\n",
    "                    j += 1\n",
    "                elif y + z > T:\n",
    "                    k -= 1\n",
    "                else: # x+y+z == T, now calculate the size of the contribution\n",
    "                    if i < j < k:\n",
    "                        ans += count[x] * count[y] * count[z]\n",
    "                    elif i == j < k:\n",
    "                        ans += count[x] * (count[x] - 1) // 2 * count[z]\n",
    "                    elif i < j == k:\n",
    "                        ans += count[x] * count[y] * (count[y] - 1) // 2\n",
    "                    else:  # i == j == k\n",
    "                        ans += count[x] * (count[x] - 1) * (count[x] - 2) // 6\n",
    "\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def threeSumMulti(self, A: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        count = collections.Counter(A)\n",
    "        keys = sorted(count)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # Now, let's do a 3sum on \"keys\", for i <= j <= k.\n",
    "        # We will use count to add the correct contribution to ans.\n",
    "        for i, x in enumerate(keys):\n",
    "            T = target - x\n",
    "            j, k = i, len(keys) - 1\n",
    "            while j <= k:\n",
    "                y, z = keys[j], keys[k]\n",
    "                if y + z < T:\n",
    "                    j += 1\n",
    "                elif y + z > T:\n",
    "                    k -= 1\n",
    "                else: # x+y+z == T, now calculate the size of the contribution\n",
    "                    if i < j < k:\n",
    "                        ans += count[x] * count[y] * count[z]\n",
    "                    elif i == j < k:\n",
    "                        ans += count[x] * (count[x] - 1) / 2 * count[z]\n",
    "                    elif i < j == k:\n",
    "                        ans += count[x] * count[y] * (count[y] - 1) / 2\n",
    "                    else:  # i == j == k\n",
    "                        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6\n",
    "\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "\n",
    "        return int(ans % MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def threeSumMulti(self, A, target):\n",
    "        MOD = 10**9 + 7\n",
    "        count = collections.Counter(A)\n",
    "        keys = sorted(count)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # Now, let's do a 3sum on \"keys\", for i <= j <= k.\n",
    "        # We will use count to add the correct contribution to ans.\n",
    "        for i, x in enumerate(keys):\n",
    "            T = target - x\n",
    "            j, k = i, len(keys) - 1\n",
    "            while j <= k:\n",
    "                y, z = keys[j], keys[k]\n",
    "                if y + z < T:\n",
    "                    j += 1\n",
    "                elif y + z > T:\n",
    "                    k -= 1\n",
    "                else: # x+y+z == T, now calculate the size of the contribution\n",
    "                    if i < j < k:\n",
    "                        ans += count[x] * count[y] * count[z]\n",
    "                    elif i == j < k:\n",
    "                        ans += count[x] * (count[x] - 1) / 2 * count[z]\n",
    "                    elif i < j == k:\n",
    "                        ans += count[x] * count[y] * (count[y] - 1) / 2\n",
    "                    else:  # i == j == k\n",
    "                        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6\n",
    "\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "\n",
    "        return int(ans % MOD)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumMulti(self, arr: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        count = collections.Counter(arr)\n",
    "        keys = sorted(count)\n",
    "        \n",
    "        ans = 0\n",
    "        \n",
    "        # Now, let's do a 3sum on \"keys\", for i <= j <= k.\n",
    "        # We will use count to add the correct contribution to ans.\n",
    "        for i, x in enumerate(keys):\n",
    "            T = target - x\n",
    "            j, k = i, len(keys) - 1\n",
    "            while j <= k:\n",
    "                y, z = keys[j], keys[k]\n",
    "                if y + z < T:\n",
    "                    j += 1\n",
    "                elif y + z > T:\n",
    "                    k -= 1\n",
    "                else: # x+y+z == T, now calculate the size of the contribution\n",
    "                    if i < j < k:\n",
    "                        ans += count[x] * count[y] * count[z]\n",
    "                    elif i == j < k:\n",
    "                        ans += count[x] * (count[x] - 1) / 2 * count[z]\n",
    "                    elif i < j == k:\n",
    "                        ans += count[x] * count[y] * (count[y] - 1) / 2\n",
    "                    else:\n",
    "                        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6\n",
    "\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "                    \n",
    "        return int(ans % MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def threeSumMulti(self, A, target):\n",
    "        MOD = 10**9 + 7\n",
    "        count = collections.Counter(A)\n",
    "        print(count)\n",
    "        keys = sorted(count)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # Now, let's do a 3sum on \"keys\", for i <= j <= k.\n",
    "        # We will use count to add the correct contribution to ans.\n",
    "        for i, x in enumerate(keys):\n",
    "            T = target - x\n",
    "            j, k = i, len(keys) - 1\n",
    "            while j <= k:\n",
    "                y, z = keys[j], keys[k]\n",
    "                if y + z < T:\n",
    "                    j += 1\n",
    "                elif y + z > T:\n",
    "                    k -= 1\n",
    "                else: # x+y+z == T, now calculate the size of the contribution\n",
    "                    if i < j < k:\n",
    "                        ans += count[x] * count[y] * count[z]\n",
    "                    elif i == j < k:\n",
    "                        ans += count[x] * (count[x] - 1) / 2 * count[z]\n",
    "                    elif i < j == k:\n",
    "                        ans += count[x] * count[y] * (count[y] - 1) / 2\n",
    "                    else:  # i == j == k\n",
    "                        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6\n",
    "\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "\n",
    "        return int(ans % MOD)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "# nums[0] - nums[k] <= t = 10\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        n = len(nums)\n",
    "        sort_list = SortedList([])\n",
    "        idx_diff, value_diff = k, t\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # calculate \n",
    "            lower = nums[i] - value_diff\n",
    "            upper = nums[i] + value_diff\n",
    "            l = sort_list.bisect_left(lower)\n",
    "            r = sort_list.bisect_right(upper)\n",
    "            ans += r-l\n",
    "\n",
    "            # slide window \n",
    "            sort_list.add(nums[i])\n",
    "            if i-idx_diff >= 0:\n",
    "                sort_list.remove(nums[i-idx_diff])\n",
    "\n",
    "        return ans >= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "\n",
    "        def calculate(num1:int,num2:int,flag:str)->int:\n",
    "            if flag == \"+\":\n",
    "                return  num1+num2\n",
    "            elif  flag == '-':\n",
    "                return num1 - num2\n",
    "            elif  flag == '*':\n",
    "                return num1 *num2\n",
    "            elif flag == '/':\n",
    "                f =  -1 if num1 *num2 <0 else 1\n",
    "                return abs(num1)//abs(num2)*f\n",
    "\n",
    "        st = deque()\n",
    "        for token in tokens:\n",
    "            if  token  in ('+','-','*','/'):\n",
    "                num1 = int(st.pop())\n",
    "                num2 = int(st.pop())\n",
    "                t = calculate(num2,num1,token)\n",
    "                st.append(t)\n",
    "            else:\n",
    "                st.append(token)\n",
    "\n",
    "        return int(st.pop())\n",
    "        \n",
    "\n",
    "        \n",
    "   \n",
    " \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        dist = [[[0 for i in range(k + 1)] for i in range(len(houses))] for i in range(len(houses))]\n",
    "        for i in range(len(houses)):\n",
    "            for j in range(i, len(houses)):\n",
    "                if i == j:\n",
    "                    dist[i][j][1] = 0\n",
    "                elif i == j - 1:\n",
    "                    dist[i][j][1] = houses[j] - houses[i]\n",
    "                else:\n",
    "                    dist[i][j][1] = self.calculate_distance(houses[i:j+1], houses[i + (j - i) // 2])\n",
    "        for kk in range(2, k):\n",
    "            for i in range(len(houses)):\n",
    "                for j in range(i + kk - 1, len(houses)):\n",
    "                    min_dist = -1\n",
    "                    for pivot in range(i + kk - 1, j + 1):\n",
    "                        if min_dist == -1 or min_dist > dist[i][pivot - 1][kk-1] + dist[pivot][j][1]:\n",
    "                            min_dist = dist[i][pivot - 1][kk-1] + dist[pivot][j][1]\n",
    "                    dist[i][j][kk] = min_dist\n",
    "        if k > 1:\n",
    "            min_dist = -1\n",
    "            for pivot in range(k - 1, len(houses)):\n",
    "                if min_dist == -1 or min_dist > dist[0][pivot - 1][k-1] + dist[pivot][len(houses) - 1][1]:\n",
    "                    min_dist = dist[0][pivot - 1][k-1] + dist[pivot][len(houses) - 1][1]\n",
    "            dist[0][len(houses) - 1][k] = min_dist\n",
    "        return dist[0][len(houses) - 1][k]\n",
    "\n",
    "    def calculate_distance(self, houses: List[int], post_box : int) -> int:\n",
    "        dist = 0\n",
    "        for house in houses:\n",
    "            dist += abs(house - post_box)\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1] + nums + [1]\n",
    "        n = len(nums)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        def calculate(i: int, j: int) -> int:\n",
    "            if dp[i][j] or j == i + 1:\n",
    "                return dp[i][j]\n",
    "            coins = 0\n",
    "            for k in range(i + 1, j):\n",
    "                coins = max(coins, nums[i] * nums[k] * nums[j] + calculate(i, k) + calculate(k, j))\n",
    "            dp[i][j] = coins\n",
    "            return coins\n",
    "\n",
    "        return calculate(0, n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        res=pre=0\n",
    "        for m,r in brackets:\n",
    "            if  income <=m:\n",
    "                res += (income-pre)*r\n",
    "                break\n",
    "            res += (m-pre)*r\n",
    "            pre = m\n",
    "        return res/100 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        pre = 0\n",
    "        for up,per in brackets:\n",
    "            ans += (min(up, income) - pre) * per * 0.01\n",
    "            if income <= up:\n",
    "                break\n",
    "            pre = up\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        totalTax = lower = 0\n",
    "        for upper, percent in brackets:\n",
    "            tax = (min(income, upper) - lower) * percent\n",
    "            totalTax += tax\n",
    "            if income <= upper:\n",
    "                break\n",
    "            lower = upper\n",
    "        return totalTax / 100\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        tax = 0\n",
    "        brackets.insert(0,[0,0])\n",
    "        for i in range(1,len(brackets)):\n",
    "            if brackets[i][0] <= income:\n",
    "                tax += (brackets[i][0] - brackets[i-1][0]) * brackets[i][1] / 100\n",
    "            else:\n",
    "                tax += (income - brackets[i-1][0]) * brackets[i][1] / 100\n",
    "                break\n",
    "        return tax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        a=b=i=0\n",
    "        while brackets[i][0]<income:\n",
    "            a+=brackets[i][1]*(brackets[i][0]-b)/100\n",
    "            b=brackets[i][0]\n",
    "            i+=1\n",
    "        a+=brackets[i][1]*(income-b)/100\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        p = 0\n",
    "        for i,j in brackets:\n",
    "            if income > i:\n",
    "                ans += (i - p) * j/100\n",
    "                p = i\n",
    "            else:\n",
    "                ans += (income - p) *j/100\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        b_index = 0\n",
    "        ans = 0\n",
    "        while b_index < len(brackets) and income > 0:\n",
    "            u, p = brackets[b_index]\n",
    "            if b_index == 0:\n",
    "                ans += min(u, income) * (p / 100)\n",
    "                income = income - u\n",
    "            else:\n",
    "                ans += min(u - brackets[b_index - 1][0], income) * (p / 100)\n",
    "                income = income - (u - brackets[b_index - 1][0])\n",
    "            b_index += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        re = 0\n",
    "        pre = 0\n",
    "        for upper, per in brackets:\n",
    "            if income < upper:\n",
    "                re += (income-pre) * per * 0.01\n",
    "                break\n",
    "            re += (upper-pre) * per * 0.01\n",
    "            pre = upper\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        tax_sum = 0\n",
    "        n = len(brackets)\n",
    "        if income >= brackets[0][0]:\n",
    "            for i in range(1,n):\n",
    "                if income >= brackets[i][0]:\n",
    "                    tax_sum += (brackets[i][0]-brackets[i-1][0]) * brackets[i][1]/100\n",
    "                else:\n",
    "                    tax_sum += (income-brackets[i-1][0]) * brackets[i][1]/100\n",
    "                    break\n",
    "            tax_sum += brackets[0][0]*brackets[0][1]/100\n",
    "        else:\n",
    "            tax_sum = income*brackets[0][1]/100\n",
    "        return tax_sum\n",
    "\n",
    "# calculateTax([[3,50],[7,10],[12,25]],10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        for i, ran in enumerate(brackets):\n",
    "            if income > ran[0]:\n",
    "                if i == 0:\n",
    "                    ans += ran[0] * ran[1] / 100\n",
    "                else:\n",
    "                    ans += (ran[0] - brackets[i-1][0]) * ran[1] / 100\n",
    "            else:\n",
    "                if i == 0:\n",
    "                    ans += income * ran[1] / 100\n",
    "                else:\n",
    "                    ans += (income - brackets[i-1][0]) * ran[1] / 100\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = prev = 0\n",
    "        for upper, percent in brackets:\n",
    "            ans += max(0, min(income, upper) - prev) * percent\n",
    "            prev = upper\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        n = len(brackets)\n",
    "        ans += min(income, brackets[0][0])*brackets[0][1]\n",
    "        for i in range(1, n):\n",
    "            cur = min(income, brackets[i][0]) - brackets[i-1][0]\n",
    "            if cur > 0:\n",
    "                ans += cur*brackets[i][1]\n",
    "        return ans/100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans, used = 0, 0\n",
    "        for row in brackets:\n",
    "            line = row[0]\n",
    "            # print(\"row={}, used={}\".format(row, used))\n",
    "            if income > line:\n",
    "                ans += ((line-used) * row[1]/100)\n",
    "                used += (line-used)\n",
    "            else:\n",
    "                ans += (income-used) * row[1]/100\n",
    "                break\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = prev = 0\n",
    "        for upper, percent in brackets:\n",
    "            ans += max(0, min(income, upper) - prev) * percent\n",
    "\n",
    "            prev = upper\n",
    "\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        pre = 0\n",
    "        for u, p in brackets:\n",
    "            if income >= pre:\n",
    "                ans += (min(u, income) - pre) * (p / 100)\n",
    "                pre = u\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if income < brackets[0][0]: return income * brackets[0][1] / 100\n",
    "        ans = brackets[0][0] * brackets[0][1] / 100\n",
    "        for i, bracket in enumerate(brackets):\n",
    "            if i == 0: continue\n",
    "            tax = bracket[0] - brackets[i-1][0] if income >= bracket[0] else income - brackets[i-1][0]\n",
    "            ans += tax * bracket[1] / 100 if tax > 0 else 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if brackets[0][0] >= income:\n",
    "            ans = income * brackets[0][1] / 100\n",
    "            income = 0\n",
    "        else:\n",
    "            ans = brackets[0][0] * brackets[0][1] / 100\n",
    "            income -= brackets[0][0]\n",
    "        i, n = 1, len(brackets)\n",
    "        while income > 0:\n",
    "            if (brackets[i][0] - brackets[i - 1][0]) >= income:\n",
    "                ans += income * brackets[i][1] / 100\n",
    "                income = 0\n",
    "            else:\n",
    "                ans += (brackets[i][0] - brackets[i - 1][0]) * brackets[i][1] / 100\n",
    "                income -= (brackets[i][0] - brackets[i - 1][0])\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans,save = 0,0\n",
    "        for b in brackets:\n",
    "            if income <= 0:\n",
    "                return ans\n",
    "            ans += min(b[0]-save,income) * b[1] / 100\n",
    "            income -= b[0]-save\n",
    "            save = b[0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, a: List[List[int]], x: int) -> float:\n",
    "        res = 0\n",
    "        pre = 0\n",
    "        for u, p in a:\n",
    "            if pre>x:\n",
    "                break\n",
    "            res += (min(u, x)-pre)*p/100\n",
    "            pre = u\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        lowest=brackets[0][0]\n",
    "        lowest_rate=brackets[0][1]\n",
    "        if lowest>=income:\n",
    "            return income*lowest_rate/100\n",
    "        res=lowest*lowest_rate/100\n",
    "        \n",
    "        for i in range(1, len(brackets)):\n",
    "            if income<=brackets[i][0]:\n",
    "                res+=((income-lowest)*brackets[i][1]/100)\n",
    "                break\n",
    "            else:\n",
    "                res+=((brackets[i][0]-lowest)*brackets[i][1]/100)\n",
    "                lowest=brackets[i][0]\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        temp = income\n",
    "        prev = 0\n",
    "        for i in brackets:\n",
    "            if temp == 0:\n",
    "                break\n",
    "            elif income >= i[0]:\n",
    "                ans += (i[0] - prev) * (i[1] * 0.01)\n",
    "                prev = i[0]\n",
    "            else:\n",
    "                ans += (income - prev )* (i[1] * 0.01)\n",
    "                break \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        totalTax=lower=0\n",
    "        for upper,percent in brackets:\n",
    "            tax=(min(income,upper)-lower)*percent\n",
    "            totalTax+=tax\n",
    "            if income<=upper:\n",
    "                break\n",
    "            lower=upper\n",
    "        return totalTax/100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        totalTax = lower = 0\n",
    "        for upper, percent in brackets:\n",
    "            tax = (min(income, upper) - lower) * percent\n",
    "            totalTax += tax\n",
    "            if income <= upper:\n",
    "                break\n",
    "            lower = upper\n",
    "        return totalTax / 100\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if income == 0:\n",
    "            return income\n",
    "        \n",
    "        if brackets[0][0]>=income:\n",
    "            money = income*brackets[0][1]/100\n",
    "            return money\n",
    "        else:\n",
    "            minus = income\n",
    "            org_income = income\n",
    "            money = brackets[0][0] * brackets[0][1] / 100\n",
    "            income -= brackets[0][0]\n",
    "            for i in range(1, len(brackets)):\n",
    "                if brackets[i][0] <= minus:\n",
    "                    # minus -= brackets[i - 1][0]\n",
    "                    income = brackets[i][0]-brackets[i - 1][0]\n",
    "                    money += (income * brackets[i][1] / 100)\n",
    "                    # print(brackets[i][0], brackets[i][1], income, money)\n",
    "                else:\n",
    "                    org_income -= brackets[i - 1][0]\n",
    "                    money += (org_income * brackets[i][1] / 100)\n",
    "                    return money\n",
    "            return money"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        totalTax = lower = 0\n",
    "        for upper, percent in brackets:\n",
    "            tax = (min(income, upper) - lower) * percent\n",
    "            totalTax += tax\n",
    "            if income <= upper:\n",
    "                break\n",
    "            lower = upper\n",
    "        return totalTax / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = pre = 0 \n",
    "        for up,rate in  brackets:\n",
    "            if  income <= up:\n",
    "                ans +=(income - pre)*rate\n",
    "                break\n",
    "            ans += (up-pre)*rate\n",
    "            pre = up\n",
    "        return  ans/100\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        totalTax = lower = 0\n",
    "        for upper,percent in brackets:\n",
    "            tax = (min(income,upper)-lower)*percent\n",
    "            totalTax += tax\n",
    "            if income<=upper:break\n",
    "            lower = upper\n",
    "        return totalTax/100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        res = income\n",
    "        ans = 0\n",
    "        last_upper = 0\n",
    "        for upper, percent in brackets:\n",
    "            if res >= upper:\n",
    "                ans += (upper-last_upper) * percent / 100\n",
    "            else:\n",
    "                ans += (res - last_upper) * percent / 100\n",
    "                return ans\n",
    "            last_upper = upper\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ret = 0\n",
    "        n = len(brackets)\n",
    "        start = 0\n",
    "        for i in range(n):\n",
    "            a, b = brackets[i]\n",
    "            if income <= a:\n",
    "                ret += (income - start) * b / 100\n",
    "                return ret\n",
    "            else:\n",
    "                ret += (a - start) * b / 100\n",
    "                start = a\n",
    "        # return ret + (income - d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if income==0:\n",
    "            return 0\n",
    "        else:\n",
    "            s=0\n",
    "            for i in range(len(brackets)):\n",
    "                if i==0:\n",
    "                    if brackets[i][0]>=income:\n",
    "                        s+=income*brackets[i][1]/100\n",
    "                        income-=income\n",
    "                    else:\n",
    "                        s+=brackets[i][0]*brackets[i][1]/100\n",
    "                        income -= brackets[i][0]\n",
    "                else:\n",
    "                    if brackets[i][0]-brackets[i-1][0] < income:\n",
    "                        s+=(brackets[i][0]-brackets[i-1][0])*brackets[i][1]/100\n",
    "                        income-=brackets[i][0]-brackets[i-1][0]\n",
    "                    else:\n",
    "                        s+=income*brackets[i][1]/100\n",
    "                        income-=income\n",
    "            return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        n = len(brackets)\n",
    "        pre = 0\n",
    "        for up,per in brackets:\n",
    "            if income >= up:\n",
    "                ans += (up - pre) * per * 0.01\n",
    "                pre = up\n",
    "            else:\n",
    "                ans += (income - pre) * per * 0.01\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if income == 0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        target = 0\n",
    "        for i in range (len(brackets)):\n",
    "            if brackets[i][0] < income:\n",
    "                count += (brackets[i][0] - target) * 0.01 * brackets[i][1]\n",
    "                target = brackets[i][0]\n",
    "            else:\n",
    "                count += (income - target) * 0.01 * brackets[i][1]\n",
    "                break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        pre = ans = 0\n",
    "        for x, y in brackets:\n",
    "            ans += max(0, min(income, x) - pre)  *  y\n",
    "            pre = x\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        tax = start = 0\n",
    "        for upper, rate in brackets:\n",
    "            if income > upper:\n",
    "                tax += (upper - start) * rate \n",
    "                start = upper\n",
    "            elif income <= upper:\n",
    "                tax += (income - start) * rate\n",
    "                break\n",
    "            # print(upper, rate, tax, start)\n",
    "        return tax / 100\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        n = len(brackets) \n",
    "        ans = 0 \n",
    "        pre = 0 \n",
    "        for i in range(n):\n",
    "            if income >= brackets[i][0]:\n",
    "                ans += (brackets[i][0]-pre) * brackets[i][1] \n",
    "                pre = brackets[i][0]\n",
    "            else:\n",
    "                ans += (income - pre) * brackets[i][1] \n",
    "                break \n",
    "        return ans / 100 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        brackets = [[0, 0]] + brackets\n",
    "        i, n = 1, len(brackets)\n",
    "        while income > 0:\n",
    "            if (brackets[i][0] - brackets[i - 1][0]) >= income:\n",
    "                ans += income * brackets[i][1] / 100\n",
    "                income = 0\n",
    "            else:\n",
    "                ans += (brackets[i][0] - brackets[i - 1][0]) * brackets[i][1] / 100\n",
    "                income -= (brackets[i][0] - brackets[i - 1][0])\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = prev = 0\n",
    "        for upper, percent in brackets:\n",
    "            ans += max(0, min(income, upper) - prev) * percent\n",
    "            prev = upper\n",
    "        return ans / 100\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        amount=0\n",
    "        lastUpper=0\n",
    "        for value in brackets:\n",
    "            amount+=(min(value[0],income)-lastUpper)*value[1]/100\n",
    "            # 更新税率上限\n",
    "            lastUpper=value[0]\n",
    "            if value[0]>=income:\n",
    "                break\n",
    "        return amount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        for i, ran in enumerate(brackets):\n",
    "            if income > ran[0]:\n",
    "                if i == 0:\n",
    "                    ans += ran[0] * ran[1]\n",
    "                else:\n",
    "                    ans += (ran[0] - brackets[i-1][0]) * ran[1]\n",
    "            else:\n",
    "                if i == 0:\n",
    "                    ans += income * ran[1]\n",
    "                else:\n",
    "                    ans += (income - brackets[i-1][0]) * ran[1]\n",
    "                break\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        brackets = [[0, 0]] + brackets\n",
    "        i, n = 1, len(brackets)\n",
    "        while income > 0:\n",
    "            if (brackets[i][0] - brackets[i - 1][0]) >= income:\n",
    "                ans += income * brackets[i][1] / 100\n",
    "                income = 0\n",
    "            else:\n",
    "                ans += (brackets[i][0] - brackets[i - 1][0]) * brackets[i][1] / 100\n",
    "                income -= (brackets[i][0] - brackets[i - 1][0])\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = prev = 0\n",
    "        for upper, percent in brackets:\n",
    "            ans += max(0, min(income, upper) - prev) * percent\n",
    "            prev = upper\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "\n",
    "        ans = prev = 0\n",
    "\n",
    "        for upper, percent in brackets:\n",
    "\n",
    "            ans += max(0, min(income, upper) - prev) * percent\n",
    "\n",
    "            prev = upper\n",
    "\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        res = 0\n",
    "        pre = 0\n",
    "        for idx,(u,p) in enumerate(brackets):\n",
    "            if u <= income:\n",
    "                res += (u-pre)*(p/100)\n",
    "                pre = u\n",
    "            else:\n",
    "                res += (income-pre)*(p/100)\n",
    "                return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        tax = 0\n",
    "        low = 0\n",
    "        for i in brackets:\n",
    "            if i[0] < income:\n",
    "                tax += (i[0] - low)*i[1]\n",
    "                low = i[0]\n",
    "            else:\n",
    "                tax += (income - low)*i[1]\n",
    "                break\n",
    "        return tax*0.01"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans=0\n",
    "        i=0\n",
    "        for i in range(len(brackets)):\n",
    "            if brackets[i][0]>=income:\n",
    "                if i==0:\n",
    "                    return income*brackets[0][1]/100\n",
    "                for j in range(i):\n",
    "                    if j==0:\n",
    "                        ans+=brackets[0][0]*brackets[0][1]/100\n",
    "                    else:\n",
    "                        ans+=(brackets[j][0]-brackets[j-1][0])*brackets[j][1]/100\n",
    "                ans+=(income-brackets[i-1][0])*brackets[i][1]/100\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        alltax = lower = 0\n",
    "        for upper , percent in brackets:\n",
    "            tax=(min(income,upper)-lower)*percent\n",
    "            alltax += tax\n",
    "            if income <= upper :\n",
    "                break;\n",
    "            lower = upper\n",
    "        return alltax/100\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        n = len(brackets)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if income < brackets[i][0]:\n",
    "                if i - 1 >= 0:\n",
    "                    diff = income - brackets[i - 1][0]\n",
    "                    ans += diff * brackets[i][1] / 100\n",
    "                else:\n",
    "                    ans += income * brackets[i][1] / 100\n",
    "                break\n",
    "            else:\n",
    "                if i == 0:\n",
    "                    ans += brackets[i][0] * brackets[i][1] / 100\n",
    "                    #print(brackets[i][0] * brackets[i][1] / 100)\n",
    "                else:\n",
    "                    diff = (brackets[i][0] - brackets[i - 1][0]) * brackets[i][1] / 100\n",
    "                    \n",
    "                    ans += diff\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        last = 0\n",
    "        for u, r in brackets:\n",
    "            if income <= last:\n",
    "                break\n",
    "            ans += (min(income, u) - last) * r / 100\n",
    "            last = u\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if income == 0:\n",
    "            return income\n",
    "        \n",
    "        if brackets[0][0]>=income:\n",
    "            money = income*brackets[0][1]/100\n",
    "            return money\n",
    "        else:\n",
    "            minus = income\n",
    "            org_income = income\n",
    "            money = brackets[0][0] * brackets[0][1] / 100\n",
    "            income -= brackets[0][0]\n",
    "            for i in range(1, len(brackets)):\n",
    "                if brackets[i][0] <= minus:\n",
    "                    # minus -= brackets[i - 1][0]\n",
    "                    income = brackets[i][0]-brackets[i - 1][0]\n",
    "                    money += (income * brackets[i][1] / 100)\n",
    "                    # print(brackets[i][0], brackets[i][1], income, money)\n",
    "                else:\n",
    "                    org_income -= brackets[i - 1][0]\n",
    "                    money += (org_income * brackets[i][1] / 100)\n",
    "                    return money\n",
    "            return money"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, b: List[List[int]], income: int) -> float:\n",
    "        if b[0][0] >= income:\n",
    "            return income * b[0][1] / 100\n",
    "        ans = b[0][0] * b[0][1]\n",
    "        for i in range(1, len(b)):\n",
    "            if b[i][0] >= income:\n",
    "                ans += (income - b[i - 1][0]) * b[i][1]\n",
    "                break\n",
    "            ans += (b[i][0] - b[i - 1][0]) * b[i][1]\n",
    "            print(b[i][0], b[i - 1][0], b[i][1])\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        ans = 0\n",
    "        p = 0\n",
    "        for upper, percent in brackets:\n",
    "            ans += max(0, min(income, upper) - p) * percent\n",
    "            p = upper\n",
    "        return ans / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        tax = 0\n",
    "        low = 0\n",
    "        for i in brackets:\n",
    "            if i[0] < income:\n",
    "                tax += (i[0] - low)*i[1]*0.01\n",
    "                low = i[0]\n",
    "            else:\n",
    "                tax += (income - low)*i[1]*0.01\n",
    "                break\n",
    "        return tax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for tax in brackets:\n",
    "            \n",
    "            upper = tax[0]\n",
    "            upper -= cur\n",
    "        \n",
    "            if upper > income:\n",
    "                res += income * tax[1] * 0.01\n",
    "                break\n",
    "            else:\n",
    "                res += upper * tax[1] * 0.01\n",
    "                \n",
    "                cur = tax[0]\n",
    "                income -= upper\n",
    "\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        totalTax = lower = 0\n",
    "        for upper, percent in brackets:\n",
    "            tax = (min(income, upper) - lower) * percent\n",
    "            totalTax += tax\n",
    "            if income <= upper:\n",
    "                break\n",
    "            lower = upper\n",
    "        return totalTax / 100\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        res = 0\n",
    "        tmp = 0\n",
    "        for bracket in brackets:\n",
    "            if income > bracket[0] - tmp:\n",
    "                res += (bracket[0] - tmp)*(bracket[1]/100.0)\n",
    "                income = income - (bracket[0] - tmp)\n",
    "                tmp = bracket[0]\n",
    "            elif income > 0:\n",
    "                res += income * (bracket[1] / 100.0)\n",
    "                income = 0\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        if len(brackets) == 0:\n",
    "            return 0\n",
    "        \n",
    "        result = 0.0\n",
    "        pre = 0\n",
    "        for bracket in brackets:\n",
    "            if income > bracket[0]:\n",
    "                result = result + (bracket[0] - pre) * bracket[1]\n",
    "                pre = bracket[0]\n",
    "            else:\n",
    "                result = result + (income - pre) * bracket[1]\n",
    "                break\n",
    "        return result / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateTax(self, brackets: List[List[int]], income: int) -> float:\n",
    "        tax = 0\n",
    "        if income == 0:\n",
    "            return 0\n",
    "        for i in range(len(brackets)):\n",
    "            if len(brackets) == 1:\n",
    "                if income - brackets[0][0] == 0:\n",
    "                    tax = brackets[0][0] * (brackets[0][1] / 100)\n",
    "                else:\n",
    "                    # tax = abs(income - brackets[0][0]) * (brackets[0][1] / 100)\n",
    "                    tax = income * (brackets[0][1] / 100)\n",
    "                break\n",
    "            else:\n",
    "                if i == 0:\n",
    "                    if income < brackets[i][0]:\n",
    "                        # return round(abs(income-brackets[0][0])* (brackets[0][1] / 100),2)\n",
    "                        return round(income* (brackets[0][1] / 100),2)\n",
    "                    else:\n",
    "                        tax = brackets[0][0] * (brackets[0][1] / 100)\n",
    "                elif income > brackets[i][0]:\n",
    "                    tax += (brackets[i][0] - brackets[i - 1][0]) * (brackets[i][1] / 100)\n",
    "                elif income == brackets[i][0]:\n",
    "                    tax += (income - brackets[i - 1][0]) * (brackets[i][1] / 100)\n",
    "                    break\n",
    "                elif income < brackets[i][0]:\n",
    "                    tax += (income - brackets[i - 1][0]) * (brackets[i][1] / 100)\n",
    "                    break\n",
    "\n",
    "        return round(tax, 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitSum(self, s: str, k: int) -> str:\n",
    "        ptn = re.compile(r'\\d{1,' + str(k) + r'}')\n",
    "        while len(s) > k: s = ptn.sub(lambda m: str(sum(map(int, m.group()))), s)\n",
    "        return s\n",
    "\n",
    "# 作者：不造轮子\n",
    "# 链接：https://leetcode.cn/problems/calculate-digit-sum-of-a-string/solutions/1428592/by-freeyourmind-xclp/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        i = 0\n",
    "        numStack = []\n",
    "        opStack = []\n",
    "        pri = {\n",
    "            \"*\": 1,\n",
    "            \"/\": 1,\n",
    "            \"+\": 2,\n",
    "            \"-\": 2,\n",
    "        }\n",
    "        def compute():\n",
    "            b,a = numStack.pop(),numStack.pop()\n",
    "            op = opStack.pop()\n",
    "            if op == \"+\":\n",
    "                numStack.append(a + b)\n",
    "            elif op == \"-\":\n",
    "                numStack.append(a - b)\n",
    "            elif op == \"*\":\n",
    "                numStack.append(a * b)\n",
    "            elif op == \"/\":\n",
    "                numStack.append(int(a / b))\n",
    "        while i < len(s):\n",
    "            if \"0\" <= s[i] <= \"9\":\n",
    "                j = i\n",
    "                while j<len(s) and \"0\" <= s[j] <= \"9\":\n",
    "                    j +=1\n",
    "                numStack.append(int(s[i:j]))\n",
    "                i = j-1\n",
    "            if s[i] == ' ':\n",
    "                i+=1\n",
    "                continue\n",
    "            elif s[i] in pri:\n",
    "                while opStack != [] and pri[opStack[-1]] <= pri[s[i]]:\n",
    "                    compute()\n",
    "                opStack.append(s[i])\n",
    "            i+=1\n",
    "        while opStack:\n",
    "            compute()\n",
    "        return numStack[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 出栈规则\n",
    "# 栈顶的优先级》=当前的优先级\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        sym_table={\n",
    "            '+':1,\n",
    "            '-':1,\n",
    "            '*':2,\n",
    "            '/':2\n",
    "        }\n",
    "        operate={\n",
    "            '+':lambda l,r:l+r,\n",
    "            '-':lambda l,r:l-r,\n",
    "            '*':lambda l,r:l*r,\n",
    "            '/':lambda l,r:int(l/r)     \n",
    "        }\n",
    "        s1=[]\n",
    "        s2=[]\n",
    "        num=0\n",
    "\n",
    "        for it in s:\n",
    "            if it==' ':\n",
    "                continue\n",
    "        \n",
    "            if it.isdigit():\n",
    "                num=num*10+int(it)\n",
    "            \n",
    "            if it in sym_table:\n",
    "                s1.append(num)\n",
    "                num=0\n",
    "\n",
    "                while s2 and sym_table[s2[-1]]>=sym_table[it]:\n",
    "                    op=s2.pop()\n",
    "                    right=s1.pop()\n",
    "                    left=s1.pop()\n",
    "                    s1.append(operate[op](left,right))\n",
    "                s2.append(it)\n",
    "        s1.append(num)\n",
    "        print(s1,s2)\n",
    "        while s2:\n",
    "            op=s2.pop()\n",
    "            right=s1.pop()\n",
    "            left=s1.pop()\n",
    "            s1.append(operate[op](left,right))    \n",
    "        \n",
    "        return s1[0]\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        def cal(x: int,y: int,op: str) ->int:\n",
    "            if op=='+':\n",
    "                return x+y\n",
    "            if op=='-':\n",
    "                return x-y\n",
    "            if op=='*':\n",
    "                return x*y\n",
    "            if op=='/':\n",
    "                return int(x/y)\n",
    "            return 0\n",
    "\n",
    "\n",
    "        # 两个栈\n",
    "        s=s.replace(' ', '')\n",
    "        if s[0]=='-':\n",
    "            s='0'+s\n",
    "\n",
    "        n=len(s)\n",
    "        nums=[]\n",
    "        ops=[]\n",
    "        # 对符号进行遍历\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if s[i] in '1234567890':\n",
    "                start=i\n",
    "                i+=1\n",
    "                while i<n and s[i] in '1234567890':\n",
    "                    i+=1\n",
    "                nums.append(int(s[start:i]))\n",
    "            else:\n",
    "                if ops!=[] and s[i] in '+-':\n",
    "                    while ops!=[]:\n",
    "                        y=nums.pop()\n",
    "                        x=nums.pop()\n",
    "                        op=ops.pop()\n",
    "                        nums.append(cal(x,y,op))\n",
    "                elif ops!=[] and s[i] in '*/':\n",
    "                    while ops!=[] and ops[-1] in '*/':\n",
    "                        y=nums.pop()\n",
    "                        x=nums.pop()\n",
    "                        op=ops.pop()\n",
    "                        nums.append(cal(x,y,op))\n",
    "                ops.append(s[i])\n",
    "                i+=1\n",
    "        while ops!=[]:\n",
    "            y=nums.pop()\n",
    "            x=nums.pop()\n",
    "            op=ops.pop()\n",
    "            nums.append(cal(x,y,op))\n",
    "        return nums[0]                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        stack=[]\n",
    "        num=0\n",
    "        prev='+'\n",
    "        n=len(s)\n",
    "        for i in range(n):\n",
    "            c=s[i]\n",
    "            if c.isdigit() and c!=' ':\n",
    "                num=num*10+ord(c)-ord('0')\n",
    "            if i==n-1 or c in '+-*/':\n",
    "                if prev=='+':\n",
    "                    stack.append(num)\n",
    "                elif prev=='-':\n",
    "                    stack.append(-num)\n",
    "                elif prev=='*':\n",
    "                    stack.append(stack.pop()*num)\n",
    "                elif prev=='/':\n",
    "                    stack.append(int(stack.pop()/num))\n",
    "                prev=c\n",
    "                num=0\n",
    "                \n",
    "        return sum(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        nstack, opstack = [], []\n",
    "        NUMS = set('0123456789')\n",
    "        OPS = set('+-*/')\n",
    "        flag = False\n",
    "        for c in s:\n",
    "            if c in NUMS:\n",
    "                if flag:\n",
    "                    m = nstack.pop()\n",
    "                    nstack.append(m * 10 + int(c))\n",
    "                else:\n",
    "                    nstack.append(int(c))\n",
    "                flag = True\n",
    "            elif c in OPS:\n",
    "                if opstack and opstack[-1] == '*':\n",
    "                    opstack.pop()\n",
    "                    m, n = nstack.pop(), nstack.pop()\n",
    "                    nstack.append(m * n)\n",
    "                elif opstack and opstack[-1] == '/':\n",
    "                    opstack.pop()\n",
    "                    m, n = nstack.pop(), nstack.pop()\n",
    "                    nstack.append(n // m)\n",
    "                opstack.append(c)\n",
    "                flag = False\n",
    "        if opstack and opstack[-1] == '*':\n",
    "            opstack.pop()\n",
    "            m, n = nstack.pop(), nstack.pop()\n",
    "            nstack.append(m * n)\n",
    "        elif opstack and opstack[-1] == '/':\n",
    "            opstack.pop()\n",
    "            m, n = nstack.pop(), nstack.pop()\n",
    "            nstack.append(n // m)\n",
    "        ans = nstack[0]\n",
    "        for i in range(len(opstack)):\n",
    "            if opstack[i] == '+':\n",
    "                ans += nstack[i+1]\n",
    "            elif opstack[i] == '-':\n",
    "                ans -= nstack[i+1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        stack=[]\n",
    "        numPos=0\n",
    "        preSign='+'\n",
    "        for i in range(len(s)+1):\n",
    "            if i==len(s) or s[i] in \"+-*/\":\n",
    "                if preSign=='+':\n",
    "                    stack.append(int(s[numPos:i]))\n",
    "                elif preSign=='-':\n",
    "                    stack.append(-int(s[numPos:i]))\n",
    "                elif preSign=='*':\n",
    "                    stack.append(stack.pop()*int(s[numPos:i]))\n",
    "                elif preSign=='/':\n",
    "                    stack.append(int(stack.pop()/int(s[numPos:i])))\n",
    "                if i<len(s):\n",
    "                    preSign=s[i]\n",
    "                numPos=i+1\n",
    "        return sum(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = s.replace(' ', '')\n",
    "\n",
    "        stk = []\n",
    "        op = '+'\n",
    "        num = 0\n",
    "\n",
    "        i = 0\n",
    "        num = 0\n",
    "        while i < len(s):\n",
    "            ch = s[i]\n",
    "            if ch.isdigit():\n",
    "                # num = 0\n",
    "                if i < len(s) and s[i].isdigit():\n",
    "                    num = num * 10 + int(int(s[i]) - int('0'))\n",
    "            if not ch.isdigit() or i == len(s) - 1:\n",
    "                if op == '+':\n",
    "                    stk.append(num)\n",
    "                elif op == '-':\n",
    "                    stk.append(-num)\n",
    "                elif op == '*':\n",
    "                    stk[-1] = stk[-1] * num\n",
    "                elif op == '/':\n",
    "                    stk[-1] = int(stk[-1] / num)\n",
    "                op = ch\n",
    "                num = 0\n",
    "            i += 1\n",
    "        return sum(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = s.replace(\" \", \"\")\n",
    "        length = len(s)\n",
    "        i = 0\n",
    "        while i < length:\n",
    "            if s[i] == \"*\" or s[i] == \"/\":\n",
    "                j = i - 1\n",
    "                while j >= 0:\n",
    "                    if s[j].isdigit():\n",
    "                        j -= 1\n",
    "                    else:\n",
    "                        break\n",
    "                j += 1\n",
    "                k = i + 1\n",
    "                while k < length:\n",
    "                    if s[k].isdigit():\n",
    "                        k += 1\n",
    "                    else:\n",
    "                        break\n",
    "                num1 = s[j:i]\n",
    "                num2 = s[i + 1:k]\n",
    "                if s[i] == \"*\":\n",
    "                    num = str(int(num1) * int(num2))\n",
    "                elif s[i] == \"/\":\n",
    "                    num = str(int(num1) // int(num2))\n",
    "                s = s[:j] + num + s[k:]\n",
    "                length += len(num) - (k - j)\n",
    "                i = j + len(num)\n",
    "            else:\n",
    "                i += 1\n",
    "        i = 1\n",
    "        while i < length:\n",
    "            if s[i] == \"+\" or s[i] == \"-\":\n",
    "                num1 = s[:i]\n",
    "                j = i + 1\n",
    "                while j < length:\n",
    "                    if s[j].isdigit():\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        break\n",
    "                num2 = s[i + 1:j]\n",
    "                if s[i] == \"+\":\n",
    "                    num = str(int(num1) + int(num2))\n",
    "                elif s[i] == \"-\":\n",
    "                    num = str(int(num1) - int(num2))\n",
    "                s = num + s[j:]\n",
    "                length += len(num) - j\n",
    "                i = 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return int(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        sign = ['+']\n",
    "        tmp = ''\n",
    "        stack = []\n",
    "        for i in s.replace(\" \",\"\") + '+0':\n",
    "            if i not in '+-*/':\n",
    "                tmp += i\n",
    "            else:\n",
    "                sig = sign.pop(0)\n",
    "                if sig == \"+\":\n",
    "                    stack.append(int(tmp))\n",
    "                if sig == \"-\":\n",
    "                    stack.append(-int(tmp))\n",
    "                if sig == \"*\":\n",
    "                    tmp = stack.pop() * int(tmp)\n",
    "                    stack.append(tmp)\n",
    "                if sig == \"/\":\n",
    "                    tmp = int(stack.pop() / int(tmp))\n",
    "                    stack.append(tmp)\n",
    "                tmp = ''\n",
    "                sign.append(i)\n",
    "        return sum(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    # \"13+2*2-9/3\"\n",
    "\n",
    "    # print(\"stack: \", stack)\n",
    "    # print(\"result: \", result)\n",
    "    # print(\"sign: \", sign)\n",
    "    # print()\n",
    "\n",
    "    # stack:  []\n",
    "    # result:  1\n",
    "    # sign:  +\n",
    "\n",
    "    # stack:  []\n",
    "    # result:  13\n",
    "    # sign:  +\n",
    "\n",
    "    # stack:  [13]\n",
    "    # result:  0\n",
    "    # sign:  +\n",
    "\n",
    "    # stack:  [13]\n",
    "    # result:  2\n",
    "    # sign:  +\n",
    "\n",
    "    # stack:  [13, 2]\n",
    "    # result:  0\n",
    "    # sign:  *\n",
    "\n",
    "    # stack:  [13, 2]\n",
    "    # result:  2\n",
    "    # sign:  *\n",
    "\n",
    "    # stack:  [13, 4]\n",
    "    # result:  0\n",
    "    # sign:  -\n",
    "\n",
    "    # stack:  [13, 4]\n",
    "    # result:  9\n",
    "    # sign:  -\n",
    "\n",
    "    # stack:  [13, 4, -9]\n",
    "    # result:  0\n",
    "    # sign:  /\n",
    "\n",
    "    # stack:  [13, 4, -9]\n",
    "    # result:  3\n",
    "    # sign:  /\n",
    "\n",
    "    # stack:  [13, 4, -3]\n",
    "    # result:  0\n",
    "    # sign:  +\n",
    "\n",
    "\n",
    "    def calculate(self, s: str) -> int:\n",
    "        sign = \"+\"\n",
    "        stack = []\n",
    "        result = 0\n",
    "\n",
    "        for ch in s + \"+\":\n",
    "            # \" \"\n",
    "            if ch == ' ':    \n",
    "                continue\n",
    "            # 123456789\n",
    "            elif ch.isdigit():\n",
    "                result = result * 10 + int(ch)\n",
    "            # + - / * \n",
    "            else:\n",
    "                if sign == \"+\":\n",
    "                    stack.append(result)\n",
    "                elif sign == \"-\":\n",
    "                    stack.append(-result)\n",
    "                elif sign == \"*\":\n",
    "                    stack.append(stack.pop() * result)\n",
    "                elif sign == \"/\":\n",
    "                    stack.append(int(stack.pop() / result))\n",
    "            \n",
    "                result = 0\n",
    "                sign = ch\n",
    "            \n",
    "            # print(\"stack: \", stack)\n",
    "            # print(\"result: \", result)\n",
    "            # print(\"sign: \", sign)\n",
    "            # print()\n",
    "            \n",
    "        return sum(stack)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s=s.replace(' ','')\n",
    "        priv={'+':0, '-':0, '*':1, '/':1}\n",
    "        ops=[]\n",
    "        out=[]\n",
    "        i=0\n",
    "        while i<len(s):\n",
    "            if s[i].isdigit():\n",
    "                j=self.tokenizer(s, i)\n",
    "                out.append(s[i:j])\n",
    "                i=j\n",
    "                continue\n",
    "            while len(ops)>0 and priv[ops[-1]]>=priv[s[i]]:\n",
    "                out.append((ops.pop()))\n",
    "            ops.append(s[i])\n",
    "            i+=1\n",
    "        \n",
    "        while len(ops)>0:\n",
    "            out.append(ops.pop())\n",
    "\n",
    "        stk=[]\n",
    "        for v in out:\n",
    "            if v.isdigit():\n",
    "                stk.append(int(v))\n",
    "            \n",
    "            else:\n",
    "                b=stk.pop()\n",
    "                a=stk.pop()\n",
    "\n",
    "                if v=='+':\n",
    "                    stk.append(a+b)\n",
    "                elif v=='-':\n",
    "                    stk.append(a-b)\n",
    "                elif v=='*':\n",
    "                    stk.append(a*b)\n",
    "                else:\n",
    "                    stk.append(int(a/b))\n",
    "        \n",
    "        return stk[-1]\n",
    "        \n",
    "        \n",
    "    def tokenizer(self, s,i):\n",
    "        while i<len(s) and s[i].isdigit():\n",
    "            i+=1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        st = list()\n",
    "        n = len(s)\n",
    "        num = 0\n",
    "        prev = '+'\n",
    "        for i in range(n):\n",
    "            if s[i].isdigit():\n",
    "                num = num * 10 + int(s[i])\n",
    "            if i == n-1 or s[i] in {'*', '/', '+', '-'}:\n",
    "                if prev == '*':\n",
    "                    st.append(st.pop() * num)\n",
    "                elif prev == '/':\n",
    "                    st.append(int(st.pop() / num))\n",
    "                elif prev == '+':\n",
    "                    st.append(num)\n",
    "                else:\n",
    "                    st.append(-num)\n",
    "                prev = s[i]\n",
    "                num = 0\n",
    "        return sum(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef calculate(self, s: str) -> int:\n",
    "\t\tn = len(s)\n",
    "\t\tstack = []\n",
    "\t\tpreSign = '+'\n",
    "\t\tnum = 0\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tif s[i] != ' ' and s[i].isdigit():\n",
    "\t\t\t\tnum = num * 10 + ord(s[i]) - ord('0')\n",
    "\t\t\tif i == n - 1 or s[i] in '+-*/':\n",
    "\t\t\t\tif preSign == '+':\n",
    "\t\t\t\t\tstack.append(num)\n",
    "\t\t\t\telif preSign == '-':\n",
    "\t\t\t\t\tstack.append(-num)\n",
    "\t\t\t\telif preSign == '*':\n",
    "\t\t\t\t\tstack.append(stack.pop() * num)\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tstack.append(int(stack.pop() / num))\n",
    "\t\t\t\tpreSign = s[i]\n",
    "\t\t\t\tnum = 0\n",
    "\t\treturn sum(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = s.replace(' ', '')\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        pre_sign = '-' if s[0] == '-' else '+'\n",
    "        num = 0\n",
    "        i = 0\n",
    "\n",
    "        while i < n:\n",
    "            while i < n and s[i].isdigit():\n",
    "                num = num * 10 + int(s[i])\n",
    "                i += 1\n",
    "            \n",
    "            if pre_sign == '+':\n",
    "                stack.append(num)\n",
    "            elif pre_sign == '-':\n",
    "                stack.append(-num)\n",
    "            elif pre_sign == '*':\n",
    "                stack.append(stack.pop() * num)\n",
    "            else:\n",
    "                # stack.append(stack.pop() // num) # 不能这样写，负数的除法会有问题\n",
    "                stack.append(int(stack.pop() / num))\n",
    "\n",
    "            if i < n :\n",
    "                pre_sign = s[i]\n",
    "            num = 0\n",
    "            i += 1\n",
    "        \n",
    "        return sum(stack)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        print(-3//2)\n",
    "        nums = ('1', '2', '3', '4', '5', '6', '7', '8', '9', '0')\n",
    "        prev_sign = '+'\n",
    "        stack = list()\n",
    "        curr = 0 \n",
    "        for c in s:\n",
    "            if c == ' ':\n",
    "                continue\n",
    "            if c not in nums:\n",
    "                # print(curr)\n",
    "                # print(stack)\n",
    "                if prev_sign == '*':\n",
    "                    stack.append(stack.pop() * curr)\n",
    "                elif prev_sign == '/':\n",
    "                    stack.append(int(stack.pop()/curr))\n",
    "                elif prev_sign == '+':\n",
    "                    stack.append(curr)\n",
    "                else:\n",
    "                    stack.append(-curr)\n",
    "                curr = 0\n",
    "                prev_sign = c\n",
    "            else:\n",
    "                curr = curr * 10 + int(c)\n",
    "        if prev_sign == '*':\n",
    "            stack.append(stack.pop() * curr)\n",
    "        elif prev_sign == '/':\n",
    "            stack.append(int(stack.pop()/curr))\n",
    "        elif prev_sign == '+':\n",
    "            stack.append(curr)\n",
    "        else:\n",
    "            stack.append(-curr)\n",
    "        return sum(stack)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        stack = []\n",
    "        s = s.replace(\" \", \"\")\n",
    "\n",
    "        num = 0\n",
    "        op = '+'\n",
    "        for c in s:\n",
    "            if c>='0' and c<='9':\n",
    "                num = num * 10 + int(c)\n",
    "            else:\n",
    "                # 这里的op是num前的符号\n",
    "                if op == \"+\":\n",
    "                    stack.append(num)\n",
    "                elif op == '-':\n",
    "                    stack.append(-1*num)\n",
    "                elif op == '*':\n",
    "                    stack[-1] = stack[-1] * num\n",
    "                elif op == '/':\n",
    "                    if stack[-1] < 0:\n",
    "                        stack[-1] = -1 * ((-1 * stack[-1]) // num)\n",
    "                    else:\n",
    "                        stack[-1] = stack[-1] // num\n",
    "\n",
    "                num = 0 \n",
    "                op = c\n",
    "        \n",
    "        if op == \"+\":\n",
    "            stack.append(num)\n",
    "        elif op == '-':\n",
    "            stack.append(-1*num)\n",
    "        elif op == '*':\n",
    "            stack[-1] = stack[-1] * num\n",
    "        elif op == '/':\n",
    "            if stack[-1] < 0:\n",
    "                stack[-1] = -1 * ((-1 * stack[-1]) // num)\n",
    "            else:\n",
    "                stack[-1] = stack[-1] // num\n",
    "\n",
    "        for i in stack:\n",
    "            print(i)\n",
    "        return sum(stack)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        stack = []\n",
    "        s += '+'\n",
    "        num = 0\n",
    "        presign = '+'\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == ' ':\n",
    "                continue\n",
    "            if s[i].isdigit():\n",
    "                num = num * 10 + ord(s[i]) - ord('0')\n",
    "            else:\n",
    "                if presign == '+': stack.append(num)\n",
    "                if presign == '-': stack.append(-num)\n",
    "                if presign == '*': stack.append(stack.pop()*num)\n",
    "                if presign == '/': stack.append(int(stack.pop()/num))\n",
    "                presign = s[i]\n",
    "                num = 0\n",
    "        return sum(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pre_sign = \"+\"\n",
    "        num = 0\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if s[i] != \" \" and s[i].isdigit():\n",
    "                num = num*10 + ord(s[i])-ord(\"0\")\n",
    "            if i == n-1 or s[i] in \"+-*/\":\n",
    "                if pre_sign == \"+\":\n",
    "                    stack.append(num)\n",
    "                elif pre_sign == \"-\":\n",
    "                    stack.append(-num)\n",
    "                elif pre_sign == \"*\":\n",
    "                    stack.append(stack.pop()*num)\n",
    "                else:\n",
    "                    stack.append(int(stack.pop()/num))\n",
    "                pre_sign = s[i]\n",
    "                num = 0\n",
    "        print(stack)\n",
    "        return sum(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        \n",
    "        def transfer(s):\n",
    "            \"\"\"\n",
    "            对于普通中缀表达式的计算，我们可以将其转化为后缀表达式再进行计算。转换方法也十分简单。只要建立一个用于存放运算符的栈，扫描该中缀表达式：\n",
    "            如果遇到数字，直接将该数字输出到后缀表达式（以下部分用「输出」表示输出到后缀表达式）；\n",
    "            如果遇到左括号，入栈；\n",
    "            如果遇到右括号，不断输出栈顶元素，直至遇到左括号（左括号出栈，但不输出）；\n",
    "            如果遇到其他运算符，不断去除所有运算优先级大于等于当前运算符的运算符，输出。最后，新的符号入栈；\n",
    "            把栈中剩下的符号依次输出，表达式转换结束\n",
    "        \"\"\"\n",
    "            ast = []\n",
    "            res = []\n",
    "            tmp = \"\"\n",
    "            for i in range(len(s)):\n",
    "                if s[i] in (\"+\",\"-\"):\n",
    "                    res.append(tmp)\n",
    "                    tmp = \"\"\n",
    "                    while ast:\n",
    "                        res.append(ast.pop())\n",
    "                    ast.append(s[i])\n",
    "                elif s[i] in (\"*\",\"/\"):\n",
    "                    res.append(tmp)\n",
    "                    tmp = \"\"\n",
    "                    while ast and ast[-1] in (\"*\",\"/\"):\n",
    "                        res.append(ast.pop())\n",
    "                    ast.append(s[i])\n",
    "                else:\n",
    "                    tmp += s[i]\n",
    "            res.append(tmp)\n",
    "            while ast:\n",
    "                res.append(ast.pop())\n",
    "            return res\n",
    "        def cal(l):\n",
    "            \"\"\"\n",
    "                对于一个后缀表达式，只需要 维护一个数字栈，每次遇到一个运算符，就取出两个栈顶元素，将运算结果重新压入栈\n",
    "            \"\"\"\n",
    "            ast = []\n",
    "            for i in range(len(l)):\n",
    "                if l[i] not in (\"+\",\"-\",\"*\",\"/\"):\n",
    "                    ast.append(l[i])\n",
    "                else:\n",
    "                    b = int(ast.pop())\n",
    "                    a = int(ast.pop())\n",
    "                    if l[i] == \"+\": ast.append(a+b)\n",
    "                    elif l[i] == \"-\": ast.append(a-b)\n",
    "                    elif l[i] == \"*\": ast.append(a*b)\n",
    "                    else: ast.append(a//b)\n",
    "            return ast[0]\n",
    "\n",
    "        # 除空格\n",
    "        s = \"\".join(s.split())\n",
    "        # print(transfer(s))\n",
    "        return int(cal(transfer(s)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = collections.deque(s)\n",
    "        num = 0\n",
    "        sign = '+'\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            char = s.popleft()\n",
    "            if char.isdigit():\n",
    "                num = num * 10 + int(char)\n",
    "            if char == '(':\n",
    "                num = self.calculate(s)\n",
    "            if (not char.isdigit() and char != ' ') or not s:\n",
    "                if sign == '+':\n",
    "                    res.append(num)\n",
    "                if sign == '-':\n",
    "                    res.append(-num)\n",
    "                if sign == '*':\n",
    "                    res.append(res.pop() * num)\n",
    "                if sign == '/':\n",
    "                    res.append(int(res.pop()/num))\n",
    "                num = 0\n",
    "                sign = char\n",
    "            \n",
    "            if char == ')':\n",
    "                break\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Deque\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 整数加减：带符号的数字放入栈中，最后求和即可\n",
    "    def calculate(self, s: str) -> int:\n",
    "        return self.helper(collections.deque(s))\n",
    "    \n",
    "    def helper(self, s: Deque[str]) -> int:\n",
    "        stk = []\n",
    "        num = 0\n",
    "        op = \"+\"\n",
    "        while len(s) > 0:\n",
    "            c = s.popleft()\n",
    "\n",
    "            # 递归进去，把括号内的当做一个数返回\n",
    "            if c == \"(\":\n",
    "                num = self.helper(s)\n",
    "\n",
    "            # 数字组合成多位\n",
    "            if c.isdigit():\n",
    "                num = 10*num + int(c)\n",
    "\n",
    "            # 遇到\")\"、op、最后一个数，要做一次运算\n",
    "            if (not c.isdigit() and c != \" \") or len(s) == 0:\n",
    "                if op == \"+\": # 一上来就是符号会走这里，放进去个0， op被刷新\n",
    "                    stk.append(num)\n",
    "                elif op == \"-\":\n",
    "                    stk.append(-num)\n",
    "                elif op == \"*\":\n",
    "                    stk[-1] *= num\n",
    "                elif op == \"/\":\n",
    "                    stk[-1] = int(stk[-1]/float(num))\n",
    "                \n",
    "                op = c\n",
    "                num = 0\n",
    "            \n",
    "            # 结束递归\n",
    "            if c == \")\":\n",
    "                break\n",
    "        return sum(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        i = 0\n",
    "        num = 0\n",
    "        lnum = []\n",
    "        lops = []\n",
    "        lops.append('+')\n",
    "        while i < len(s):\n",
    "            if s[i].isdigit():\n",
    "                while i< len(s) and s[i].isdigit():\n",
    "                    num = num*10+int(s[i])\n",
    "                    i+=1\n",
    "                lnum.append(num)\n",
    "                num = 0\n",
    "            elif s[i]== \" \":\n",
    "                i += 1\n",
    "            else: \n",
    "\n",
    "                ops = s[i]\n",
    "                # print(ops,lops[-1])\n",
    "                # print(lops[-1])\n",
    "                if not lops or lops[-1] != '*' and lops[-1] !='/':\n",
    "                    lops.append(ops)\n",
    "                else:\n",
    "                    num1 = lnum.pop()\n",
    "                    num2 = lnum.pop()\n",
    "                    ops0 = lops.pop()\n",
    "                    # print(num1,num2,ops0)\n",
    "                    if ops0 == '*':\n",
    "                        lnum.append(num1*num2)\n",
    "                    else:\n",
    "                        lnum.append(num2//num1)\n",
    "                    lops.append(ops)\n",
    "                i+=1\n",
    "        print(lops)\n",
    "        print(lnum)\n",
    "        ans = 0\n",
    "        for i in range(len(lops)):\n",
    "            ops = lops.pop()\n",
    "            \n",
    "            if ops == '+':\n",
    "                num = lnum.pop()\n",
    "                ans += num\n",
    "            elif ops == '-':\n",
    "                num = lnum.pop()\n",
    "                ans -= num\n",
    "            elif ops == '*':\n",
    "                num1 = lnum.pop()\n",
    "                num2 = lnum.pop()\n",
    "                lnum.append(num1*num2)\n",
    "            else:\n",
    "                num1 = lnum.pop()\n",
    "                num2 = lnum.pop()\n",
    "                lnum.append(num2//num1)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        st = []\n",
    "        ch = ['@']\n",
    "        num = ''\n",
    "        s =s + '@'\n",
    "        for c in s:\n",
    "            if c in '+-*/@':  \n",
    "                st.append(int(num))\n",
    "                if ch[-1] == '*':\n",
    "                    a = st[-1]*st[-2]\n",
    "                    st.pop()\n",
    "                    st.pop()\n",
    "                    st.append(a)\n",
    "                    ch.pop()\n",
    "                elif ch[-1] == '/':\n",
    "                    a = st[-2]//st[-1]\n",
    "                    st.pop()\n",
    "                    st.pop()\n",
    "                    st.append(a)\n",
    "                    ch.pop()\n",
    "                ch.append(c)\n",
    "                num=''\n",
    "            else:\n",
    "                num=num+c\n",
    "        \n",
    "        print(st,ch)\n",
    "        for i in range(1,len(ch)-1):\n",
    "            if ch[i] == '+':\n",
    "                st[0]+=st[i]\n",
    "            elif ch[i] == '-':\n",
    "                st[0]-=st[i]\n",
    "        return st[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        # line = 'asdf fjdk; afed, fjek,asdf, foo'\n",
    "        nums = re.split(r'\\s*[\\+-/\\*]\\s*', s)\n",
    "        op = list(filter(lambda c: c in '+-*/', s))\n",
    "        t = [int(nums[0])]\n",
    "        for i in range(1, len(nums)):\n",
    "            c = op[i - 1]\n",
    "            x = int(nums[i])\n",
    "            if c == '+':\n",
    "                t.append(x)\n",
    "            elif c == '-':\n",
    "                t.append(-x)\n",
    "            elif c == '*':\n",
    "                t[-1] *= x\n",
    "            else:\n",
    "                t[-1] /= x\n",
    "                t[-1] = int(t[-1])\n",
    "        return sum(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 64 ms ... 96 % ... 19.6 MB ... 18 %\n",
    "        #  time: O(n)\n",
    "        # space: O(n)\n",
    "        \n",
    "        s = s.replace('+', ' + ').replace('-', ' - ').replace('*', ' * ').replace('/', ' / ')\n",
    "        A = s.split()\n",
    "        stack = []\n",
    "        for sec in A:\n",
    "            if sec in '+-*/':\n",
    "                stack.append(sec)\n",
    "            elif stack and stack[-1] in '*/':\n",
    "                op = stack.pop()\n",
    "                prev = stack.pop()\n",
    "                if op == '*':\n",
    "                    stack.append(prev * int(sec))\n",
    "                else:\n",
    "                    stack.append(prev // int(sec))\n",
    "            else:\n",
    "                stack.append(int(sec))\n",
    "        res = stack[0]\n",
    "        for i in range(1, len(stack), 2):\n",
    "            if stack[i] == '+':\n",
    "                res += stack[i+1]\n",
    "            else:\n",
    "                res -= stack[i+1]\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s=s.replace(' ','')\n",
    "        if len(s)==0:\n",
    "            return None\n",
    "\n",
    "        opstack, stack = [], []\n",
    "        res = 0\n",
    "        tmp = ''\n",
    "        s=s.strip()\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i].isdigit():\n",
    "                tmp += s[i]\n",
    "                if i != len(s)-1 and s[i+1] not in [\"+\", \"-\", \"*\", \"/\"]:\n",
    "                    continue\n",
    "                if (opstack == [] or opstack[-1] == '+' or opstack[-1] == '-'):\n",
    "                    stack.append(tmp)\n",
    "                else:\n",
    "                    v1 = stack[-1]\n",
    "                    op = opstack[-1]\n",
    "                    stack.pop()\n",
    "                    opstack.pop()\n",
    "                    if op == '*':\n",
    "                        res = int(v1)*int(tmp)\n",
    "                    elif op == '/':\n",
    "                        res = (int)(int(v1) / int(tmp))\n",
    "\n",
    "                    stack.append(res)\n",
    "            elif s[i] in [\"+\", \"-\", \"*\", \"/\"]:\n",
    "                opstack.append(s[i])\n",
    "                tmp=''\n",
    "            continue\n",
    "        print(opstack,stack)\n",
    "        if (len(opstack) > 0):\n",
    "            result = int(stack[0])\n",
    "            j = 0\n",
    "            while (j < len(opstack)):\n",
    "                if opstack[j] == '+':\n",
    "                    result += int(stack[j+1])\n",
    "                else:\n",
    "                    result -= int(stack[j+1])\n",
    "                j += 1\n",
    "            return result\n",
    "        else:\n",
    "            return int(stack[-1])\n",
    "                        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef calculate(self, s: str) -> int:\n",
    "\t\ts = s.replace(' ', '')\n",
    "\t\tstack = []\n",
    "\t\ttemp = ''\n",
    "\t\tfor i in range(len(s)):\n",
    "\t\t\tch = s[i]\n",
    "\t\t\tif ch.isdigit():\n",
    "\t\t\t\ttemp += ch\n",
    "\t\t\telse:\n",
    "\t\t\t\tstack.append(int(temp))\n",
    "\t\t\t\ttemp = ''\n",
    "\t\t\t\tstack.append(ch)\n",
    "\t\tif temp:\n",
    "\t\t\tstack.append(int(temp))\n",
    "\t\tstack2 = []\n",
    "\t\tindex = 0\n",
    "\t\twhile index < len(stack):\n",
    "\t\t\tch = stack[index]\n",
    "\t\t\tif ch == '*':\n",
    "\t\t\t\tstack2.append(stack2.pop() * stack[index + 1])\n",
    "\t\t\t\tindex += 2\n",
    "\t\t\telif ch == '/':\n",
    "\t\t\t\tstack2.append(stack2.pop() // stack[index + 1])\n",
    "\t\t\t\tindex += 2\n",
    "\t\t\telse:\n",
    "\t\t\t\tstack2.append(ch)\n",
    "\t\t\t\tindex += 1\n",
    "\t\tres = stack2[0]\n",
    "\t\tfor i in range(1, len(stack2), 2):\n",
    "\t\t\tch = stack2[i]\n",
    "\t\t\tif ch == '+':\n",
    "\t\t\t\tres += stack2[i + 1]\n",
    "\t\t\telse:\n",
    "\t\t\t\tres -= stack2[i + 1]\n",
    "\t\treturn res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        st = list()\n",
    "        i = 0\n",
    "        n = len(s)\n",
    "        sign = {'+', '-', '*', '/'}\n",
    "        while i < n:\n",
    "            if s[i].isdigit():\n",
    "                num = ''\n",
    "                while i < n and s[i].isdigit():\n",
    "                    num += s[i]\n",
    "                    i += 1\n",
    "                if st and st[-1] in {'*', '/'}:\n",
    "                    sn = st.pop()\n",
    "                    if sn == '*': st.append(st.pop() * int(num))\n",
    "                    else: st.append(st.pop() // int(num))\n",
    "                else:\n",
    "                    st.append(int(num))\n",
    "                i -= 1\n",
    "            elif s[i] in sign:\n",
    "                st.append(s[i])\n",
    "            i += 1\n",
    "        st = st[::-1]\n",
    "        # print(st)\n",
    "        while len(st) > 1:\n",
    "            a = st.pop()\n",
    "            b = st.pop()\n",
    "            c = st.pop()\n",
    "            if b == '+': st.append(c + a)\n",
    "            else: st.append(a - c)\n",
    "        return st[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def calculate(self, s):\n",
    "        def dfs(q) -> int:\n",
    "            stk = []\n",
    "            preSign = '+'\n",
    "            num = 0\n",
    "\n",
    "            while q:\n",
    "                c = q.popleft()\n",
    "                if c.isdigit():\n",
    "                    num = 10 * num + int(c)\n",
    "                elif c == '(':\n",
    "                    num = dfs(q)\n",
    "                elif c in {'+', '-', '*', '/', ')'}:\n",
    "                    if preSign == '+':\n",
    "                        stk.append(num)\n",
    "                    elif preSign == '-':\n",
    "                        stk.append(-num)\n",
    "                    elif preSign == '*':\n",
    "                        stk[-1] = stk[-1] * num\n",
    "                    elif preSign == '/':\n",
    "                        stk[-1] = int(stk[-1] / num)\n",
    "                    num = 0\n",
    "                    preSign = c\n",
    "                    if c == ')':\n",
    "                        break\n",
    "                        \n",
    "            return sum(stk)\n",
    "\n",
    "        q = deque(list(s) + ['+'])\n",
    "        return dfs(q)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        stack = []\n",
    "        op_dict = {\"+\":\"__add__\",\"-\":\"__sub__\",\"*\":\"__mul__\",\"/\":\"__floordiv__\"}\n",
    "        soon = {\"*\",\"/\"}\n",
    "        slow = 0\n",
    "        fast = 0\n",
    "        s = s.replace(\" \",\"\")\n",
    "        s_len = len(s)\n",
    "        \n",
    "        while fast< s_len:\n",
    "            t = s[fast]\n",
    "            if t in op_dict:\n",
    "                if t in soon:\n",
    "                    if slow< fast:\n",
    "                        pre = int(s[slow:fast])\n",
    "                    else:\n",
    "                        pre = stack.pop()\n",
    "                    t_fast = fast+1\n",
    "                    while t_fast<s_len and s[t_fast] not in op_dict:\n",
    "                        t_fast+=1\n",
    "                    suf = int(s[fast+1:t_fast])\n",
    "                    stack.append(getattr(pre, op_dict.get(t))(suf))\n",
    "                    slow = t_fast+1\n",
    "                    fast = t_fast-1\n",
    "                else:\n",
    "                    if slow< fast:\n",
    "                        stack.append(int(s[slow:fast]))\n",
    "                    \n",
    "                    stack.append(t)\n",
    "                    slow = fast+1\n",
    "            fast+=1\n",
    "        if slow < s_len:\n",
    "            stack.append(int(s[slow:fast]))\n",
    "        # print(stack)\n",
    "        stack = stack[::-1]\n",
    "        ans = stack.pop()\n",
    "        while stack:\n",
    "            t = stack.pop()\n",
    "            ans = getattr(ans, op_dict.get(t))(stack.pop())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        # 在此添加你的代码\n",
    "        s = s.strip(\" \")\n",
    "        print(s)\n",
    "        digit_list = re.findall(r'\\d+|\\S', s)\n",
    "        digit_list = [int(ch) if ch.isdigit() else ch for ch in digit_list]\n",
    "        print(digit_list)\n",
    "        stack = []\n",
    "        stack1 = []\n",
    "        i = j = 0\n",
    "        while i < len(digit_list):\n",
    "            if digit_list[i] in [\"*\", \"/\"]:\n",
    "                op = digit_list[i]\n",
    "                num1 = stack.pop()\n",
    "                num2 = digit_list[i + 1]\n",
    "                ret = self.cal_op(op, num1, num2)\n",
    "                stack.append(ret)\n",
    "                i += 1\n",
    "            else:\n",
    "                stack.append(digit_list[i])\n",
    "            i += 1\n",
    "\n",
    "        while j < len(stack):\n",
    "            if stack[j] in [\"+\",\"-\"]:\n",
    "                op = stack[j]\n",
    "                num1 = stack1.pop()\n",
    "                num2 = stack[j + 1]\n",
    "                ret = self.cal_op(op, num1, num2)\n",
    "                stack1.append(ret)\n",
    "                j += 1\n",
    "            else:\n",
    "                stack1.append(stack[j])\n",
    "            j += 1\n",
    "\n",
    "        return stack1[0]\n",
    "\n",
    "    def cal_op(self, op, num1, num2):\n",
    "        if op == \"+\":\n",
    "            return num1 + num2\n",
    "        elif op == \"-\":\n",
    "            return num1 - num2\n",
    "        elif op == \"*\":\n",
    "            return num1 * num2\n",
    "        else:\n",
    "            return num1 // num2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        import re\n",
    "        s = s.replace(' ', '')\n",
    "        def parse_expression(expression):\n",
    "            # 使用正则表达式匹配数字和运算符\n",
    "            pattern = r\"(\\d+|-|\\/|\\*|\\+)\"\n",
    "            matches = re.findall(pattern, expression)\n",
    "            # 将匹配结果转换为目标列表\n",
    "            result = []\n",
    "            for match in matches:\n",
    "                if match.isdigit():\n",
    "                    result.append(match)\n",
    "                else:\n",
    "                    result.append(match)\n",
    "            return result\n",
    "        def isdigits(k):\n",
    "            if k.isdigit():\n",
    "                return True\n",
    "            elif k[1:].isdigit():  # -11这种情况\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "            if isdigits(s):\n",
    "                return int(s)\n",
    "        def biaoda(slst):\n",
    "            n = len(slst)\n",
    "            st = []\n",
    "            for i in range(n):\n",
    "                if isdigits(slst[i]):  # 如果是数字，直接压入栈\n",
    "                    st.append(slst[i])\n",
    "                else:\n",
    "                    if slst[i] == '+':  # 如果是运算符\n",
    "                        top1 = st.pop()\n",
    "                        top2 = st.pop()  # 栈顶两个元素pop出来，和运算符做运算\n",
    "                        tmp = float(top2) + float(top1)\n",
    "                        st.append(str(tmp))\n",
    "                    if slst[i] == '-':\n",
    "                        top1 = st.pop()\n",
    "                        top2 = st.pop()\n",
    "                        tmp = float(top2) - float(top1)\n",
    "                        st.append(str(tmp))\n",
    "                    if slst[i] == '*':\n",
    "                        top1 = st.pop()\n",
    "                        top2 = st.pop()\n",
    "                        tmp = float(top2) * float(top1)\n",
    "                        st.append(str(tmp))\n",
    "                    if slst[i] == '/':\n",
    "                        top1 = st.pop()\n",
    "                        top2 = st.pop()\n",
    "                        tmp = float(top2) / float(top1)\n",
    "                        st.append(str(int(tmp)))\n",
    "            return float(st[0])\n",
    "        s=parse_expression(s)\n",
    "        st = []\n",
    "        n = len(s)\n",
    "        nipolan = []\n",
    "        precedence = {'+': 1, '-': 1, '*': 2, '/': 2}  # 优先级\n",
    "        for i in range(n):\n",
    "            if s[i] == ' ':\n",
    "                continue\n",
    "            elif isdigits(s[i]):\n",
    "                nipolan.append(s[i])\n",
    "            else:\n",
    "                while st and precedence[s[i]] <= precedence.get(st[-1], 0):\n",
    "                    nipolan.append(st.pop())\n",
    "                st.append(s[i])\n",
    "        while st:\n",
    "            nipolan.append(st.pop())\n",
    "        return int(biaoda(nipolan))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s.replace(\" \",\"\")\n",
    "        le=len(s)\n",
    "        operation=['+','-','*','/']\n",
    "        operationfir=['*','/']\n",
    "        operationsec=['+','-']\n",
    "        cnt=0\n",
    "        stack=[]\n",
    "        for i in range(0,le):\n",
    "            if s[i] in operation:\n",
    "                cnt+=1\n",
    "        nums=['']*(2*cnt+1)\n",
    "        cnt=0\n",
    "        for i in range(0,le):\n",
    "            if s[i] in operation:\n",
    "                cnt+=1\n",
    "                nums[2*cnt-1]=s[i]\n",
    "            if s[i] not in operation:\n",
    "                nums[2*cnt]=nums[2*cnt]+s[i]\n",
    "        for i in range(0,2*cnt+1):\n",
    "            if nums[i]not in operation:\n",
    "                nums[i]=int(nums[i])\n",
    "        ptr=0\n",
    "        while ptr<2*cnt+1:\n",
    "            if nums[ptr]==\"*\":\n",
    "                stack.append(stack.pop()*nums[ptr+1])\n",
    "                ptr=ptr+2\n",
    "            elif nums[ptr]==\"/\":\n",
    "                stack.append(stack.pop()//nums[ptr+1])\n",
    "                ptr=ptr+2\n",
    "            else:\n",
    "                stack.append(nums[ptr])\n",
    "                ptr=ptr+1\n",
    "        result=stack[0]\n",
    "        for i in range(0,len(stack)):\n",
    "            if stack[i]=='+':\n",
    "                result=result+stack[i+1]\n",
    "            elif stack[i]=='-':\n",
    "                result=result-stack[i+1]\n",
    "        return result\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        def evalRPN(tokens: List[str]) -> int:\n",
    "            stack =[]\n",
    "            for token in tokens:\n",
    "                if token == '+':\n",
    "                    a = stack.pop()\n",
    "                    b = stack.pop()\n",
    "                    stack.append(b + a)\n",
    "                elif token == '-':\n",
    "                    a = stack.pop()\n",
    "                    b = 0 if not stack else stack.pop()\n",
    "                    stack.append(b - a)\n",
    "                elif token == '*':\n",
    "                    a = stack.pop()\n",
    "                    b = stack.pop()\n",
    "                    stack.append(b * a)\n",
    "                elif token == '/':\n",
    "                    a = stack.pop()\n",
    "                    b = stack.pop()\n",
    "                    stack.append(int(b/a))\n",
    "                else:\n",
    "                    stack.append(int(token))\n",
    "            return stack[-1]\n",
    "        precedence = {\n",
    "            '+': 1,\n",
    "            '-': 1,\n",
    "            '*': 2,\n",
    "            '/': 2,\n",
    "        }\n",
    "        # 转换为波兰表达式\n",
    "        stack = []\n",
    "        rpn = [0]\n",
    "        # 去除空格\n",
    "        s = s.replace(\" \", \"\")\n",
    "        tokens = list(s)\n",
    "        i = 0\n",
    "        while i < len(tokens):\n",
    "            token = tokens[i]\n",
    "            if token.isdigit():\n",
    "                j = i + 1\n",
    "                while j < len(tokens) and tokens[j].isdigit():\n",
    "                    token += tokens[j]\n",
    "                    j += 1\n",
    "                i = j-1\n",
    "                rpn.append(token)\n",
    "            else:\n",
    "                # 操作符 栈中的操作符保保持从小到大\n",
    "                while stack and precedence[token] <= precedence.get(stack[-1], 0):\n",
    "                    rpn.append(stack.pop())\n",
    "                stack.append(token)\n",
    "            i += 1\n",
    "        while stack:\n",
    "            rpn.append(stack.pop())\n",
    "        return evalRPN(rpn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s=s.replace(' ','')\n",
    "        \n",
    "        # 只含有乘除的运算\n",
    "        def parse(s):\n",
    "            opindex=[]  #存乘除符号出现的位置\n",
    "            for i,c in enumerate(s):\n",
    "                if c in '*/':\n",
    "                    opindex.append(i)\n",
    "            opindex.append(len(s))\n",
    "            res=int(s[:opindex[0]])\n",
    "            for i in range(len(opindex)-1):\n",
    "                op=s[opindex[i]]\n",
    "                num=int(s[opindex[i]+1:opindex[i+1]])\n",
    "                if op=='*':\n",
    "                    res*=num\n",
    "                else:\n",
    "                    res=res//num\n",
    "            return res\n",
    "\n",
    "        opindex=[]      # 存加减符号出现的位置\n",
    "        for i,c in enumerate(s):\n",
    "            if c in '+-':\n",
    "                opindex.append(i)\n",
    "        opindex.append(len(s))\n",
    "        res=parse(s[:opindex[0]])\n",
    "        for i in range(len(opindex)-1):\n",
    "            op=s[opindex[i]]\n",
    "            s1=s[opindex[i]+1:opindex[i+1]]\n",
    "            if op=='+':\n",
    "                res+=parse(s1)\n",
    "            else:\n",
    "                res-=parse(s1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s_new = ''\n",
    "        for i, c in enumerate(s):\n",
    "            if(c == ' '):\n",
    "                continue\n",
    "            if(i > 0 and c == '-'):\n",
    "                s_new += '+'\n",
    "            s_new += c \n",
    "        s_list = s_new.split('+')\n",
    "        def getValue(s):\n",
    "            m_flag = False\n",
    "            d_flag = False\n",
    "            for i in range(len(s)-1,-1,-1):\n",
    "                if(s[i] == '*'):\n",
    "                    m_flag = True\n",
    "                    break\n",
    "                elif(s[i] == '/'):\n",
    "                    d_flag = True \n",
    "                    break \n",
    "                else:\n",
    "                    continue\n",
    "            if(m_flag):\n",
    "                return getValue(s[:i]) * int(s[i+1:])\n",
    "            elif(d_flag):\n",
    "                num1 = getValue(s[:i])\n",
    "                num2 = int(s[i+1:])\n",
    "                if(num1 < 0 and num1 % num2 != 0):\n",
    "                    return num1 // num2 + 1\n",
    "                else:\n",
    "                    return num1 // num2\n",
    "            else:\n",
    "                return int(s)\n",
    "        result = 0\n",
    "        for c in s_list:\n",
    "            result += getValue(c)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        stack_num = []\n",
    "        stack_operator = []\n",
    "        index = 0\n",
    "        m = len(s)\n",
    "        for i in range(m):\n",
    "            if s[i] in ['+','-','*','/']:\n",
    "                stack_num.append(int(s[index:i]))\n",
    "                stack_operator.append(s[i])\n",
    "                index = i + 1\n",
    "        stack_num.append(int(s[index:]))\n",
    "        n = len(stack_operator)\n",
    "        for i in range(n):\n",
    "            if stack_operator[i] == \"*\":\n",
    "                stack_num[i + 1] *= stack_num[i]\n",
    "                if i > 0:\n",
    "                    stack_operator[i] = stack_operator[i - 1]\n",
    "                else:\n",
    "                    stack_operator[i] = '+'\n",
    "                stack_num[i] = 0\n",
    "            elif stack_operator[i] == '/':\n",
    "                if i > 0:\n",
    "                    stack_operator[i] = stack_operator[i - 1]\n",
    "                else:\n",
    "                    stack_operator[i] = '+'\n",
    "                stack_num[i + 1] = stack_num[i] // stack_num[i + 1]\n",
    "                stack_num[i] = 0\n",
    "        print(stack_num,stack_operator)\n",
    "        for i in range(n):\n",
    "            if stack_operator[i] == '+':\n",
    "                stack_num[i + 1] += stack_num[i]\n",
    "            elif stack_operator[i] == '-':\n",
    "                stack_num[i + 1] = stack_num[i] - stack_num[i + 1]\n",
    "        print(stack_num,stack_operator)\n",
    "        return stack_num[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s=s.replace(' ','').strip()\n",
    "        stack = []\n",
    "        if s.isdigit():\n",
    "            return int(''.join(s))\n",
    "\n",
    "        str = ''\n",
    "        s1 = []\n",
    "        for i in s:\n",
    "            if i not in ['*','/','+','-']:\n",
    "                str += i\n",
    "            else:\n",
    "                s1.append(''.join(str))\n",
    "                s1.append(i)\n",
    "                str=[]\n",
    "        s1.append(''.join(str))    \n",
    "        print('s1:',s1)\n",
    "        for i in range(len(s1)):\n",
    "\n",
    "            if stack and stack[-1] in ['*','/']:\n",
    "                op = stack.pop()\n",
    "                a = int(stack.pop())\n",
    "                tmp = int(a/int(s1[i])) if op == '/' else int(a*int(s1[i]))\n",
    "                stack.append(tmp)\n",
    "            else:    \n",
    "                stack.append(s1[i])\n",
    "        print(stack)\n",
    "        stack2 = []  \n",
    "        for i in range(len(stack)):\n",
    "            if stack2 and stack2[-1] in ['+','-']:\n",
    "                op = stack2.pop()\n",
    "                a = int(stack2.pop())\n",
    "                tmp = int(a+int(stack[i])) if op == '+' else int(a-int(stack[i]))\n",
    "                stack2.append(tmp)\n",
    "            else:    \n",
    "                stack2.append(stack[i])\n",
    "        print(stack2)\n",
    "        return int(stack2[0])\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s_rev=list(reversed(re.split(\"([-+*/])\",s)))#首先是将数组按照加减乘除的进行分隔符处理以-+*/进行分割\n",
    "        if len(s_rev)==1:\n",
    "            return int(s_rev[-1])\n",
    "        print(s_rev)\n",
    "        ch=[\"-\",\"+\",\"*\",\"/\"]\n",
    "        #其次如果是将将加减乘除放置一个框中，将数字放置一个框中\n",
    "        stk_num=[]\n",
    "        stk_abc=[]\n",
    "        for i in s_rev:\n",
    "            if i==\"+\" or i==\"-\":\n",
    "                #print(1,stk_num,stk_abc)\n",
    "                while len(stk_abc)>0 and (stk_abc[-1]==\"*\" or stk_abc[-1]==\"/\"):\n",
    "                    num1=stk_num.pop()\n",
    "                    num2=stk_num.pop()\n",
    "                    ch=stk_abc.pop()\n",
    "                    #print(num1,num2,ch)                                   \n",
    "                    if ch==\"*\":\n",
    "                        stk_num.append(int(num1)*int(num2))\n",
    "                    else:\n",
    "                        stk_num.append(int(int(num1)/int(num2)))\n",
    "                stk_abc.append(i)\n",
    "            elif i==\"*\" or i==\"/\":\n",
    "                stk_abc.append(i)\n",
    "            else:\n",
    "                stk_num.append(i)\n",
    "        print(stk_num,stk_abc)\n",
    "        while len(stk_abc)>0:\n",
    "\n",
    "                num1=stk_num.pop()\n",
    "                num2=stk_num.pop()\n",
    "                ch=stk_abc.pop()                   \n",
    "                if ch==\"+\":\n",
    "                    stk_num.append(int(num1)+int(num2))\n",
    "                elif ch==\"-\":\n",
    "                    stk_num.append(int(num1)-int(num2))  \n",
    "                elif ch==\"*\":\n",
    "                        stk_num.append(int(num1)*int(num2))\n",
    "                elif ch==\"/\":\n",
    "                    stk_num.append(int(int(num1)/int(num2)))      \n",
    "        return stk_num[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = s.replace(\" \",\"\").replace(\"+\",\" + \").replace(\"-\",\" -\").replace(\"*\",\" * \").replace(\"/\",\" / \").split()\n",
    "        print(s)\n",
    "        for i in range(len(s)):\n",
    "            num = s[i]\n",
    "            if num == \"+\":\n",
    "                s[i] = 0\n",
    "            elif num == \"*\":\n",
    "                s[i+1] = s[i-1] * int(s[i+1])\n",
    "                s[i-1],s[i] = 0,0\n",
    "            elif num == \"/\":\n",
    "                s[i+1] = int(s[i-1] / int(s[i+1]))\n",
    "                s[i - 1], s[i] = 0, 0\n",
    "            else:\n",
    "                s[i] = int(num)\n",
    "        return sum(s)\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = s.replace(\" \", \"\")\n",
    "        if '+' in s:\n",
    "            arr1 = s.split('+')\n",
    "        else:\n",
    "            arr1 = [s]\n",
    "        print(arr1)\n",
    "        arr2 = []\n",
    "        for i in range(len(arr1)):\n",
    "            arr3 = []\n",
    "            if '-' in arr1[i]:\n",
    "                arr3 += arr1[i].split('-')\n",
    "                arr2.append(arr3[0])\n",
    "                for j in range(1,len(arr3)):\n",
    "                    arr2.append('-' + arr3[j])\n",
    "            else:\n",
    "                arr2.append(arr1[i])\n",
    "        print(arr2)\n",
    "        arr = []\n",
    "        for i in range(len(arr2)):\n",
    "            if '*' in arr2[i] and '/' not in arr2[i]:\n",
    "                arr4 = arr2[i].split('*')\n",
    "                m = 1\n",
    "                for j in arr4:\n",
    "                    m *= int(j)\n",
    "                arr.append(m)\n",
    "            elif '/' in arr2[i] and '*' not in arr2[i]:\n",
    "                arr4 = arr2[i].split('/')\n",
    "                m = int(arr4[0])\n",
    "                for j in range(1,len(arr4)):\n",
    "                    m = int(m / int(arr4[j]))\n",
    "                arr.append(m)\n",
    "            elif '/' in arr2[i] and '*' in arr2[i]:\n",
    "                print(0)\n",
    "                res = []\n",
    "                for j in arr2[i]:\n",
    "                    if j == '*':\n",
    "                        res.append(1)\n",
    "                    elif j == '/':\n",
    "                        res.append(0)\n",
    "                print(res,arr2[i])\n",
    "                arr4 = arr2[i].split('*')\n",
    "                arr5 = []\n",
    "                for j in arr4:\n",
    "                    if '/' in j:\n",
    "                        arr5 += j.split('/')\n",
    "                    else:\n",
    "                        arr5.append(j)\n",
    "                m = int(arr5[0])\n",
    "                for j in range(1,len(arr5)):\n",
    "                    if res[j - 1] == 1:\n",
    "                        m *= int(arr5[j])\n",
    "                    else:\n",
    "                        m = int(m / int(arr5[j]))\n",
    "                arr.append(m)\n",
    "            else:\n",
    "                arr.append(int(arr2[i]))\n",
    "        return sum(arr)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = s.replace(\" \",\"\").replace(\"+\",\" + \").replace(\"-\",\" -\").replace(\"*\",\" * \").replace(\"/\",\" / \").split()\n",
    "        for i in range(len(s)):\n",
    "            num = s[i]\n",
    "            if num == \"+\":\n",
    "                s[i] = 0\n",
    "            elif num == \"*\":\n",
    "                s[i+1] = s[i-1] * int(s[i+1])\n",
    "                s[i-1],s[i] = 0,0\n",
    "            elif num == \"/\":\n",
    "                s[i+1] = int(s[i-1] / int(s[i+1]))\n",
    "                s[i - 1], s[i] = 0, 0\n",
    "            else:\n",
    "                s[i] = int(num)\n",
    "        return sum(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        \"\"\"巧妙利用sum()和0，效率较高\"\"\"\n",
    "        s = s.replace(' ','').replace('+',' + ').replace('-',' -').replace('*',' * ').replace('/',' / ')\n",
    "        val = s.split()\n",
    "        for i in range(len(val)):\n",
    "            if val[i]=='*':\n",
    "                val[i+1] = val[i-1]*int(val[i+1])\n",
    "                val[i],val[i-1] = 0,0\n",
    "            elif val[i]=='/':\n",
    "                val[i+1] = int(val[i-1]/int(val[i+1]))\n",
    "                val[i],val[i-1] = 0,0\n",
    "            elif val[i]=='+':\n",
    "                val[i] = 0\n",
    "            else:\n",
    "                val[i] = int(val[i])\n",
    "        return sum(val)\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        def split():\n",
    "            ops = []\n",
    "            last = 0\n",
    "            for i in range(len(s)):\n",
    "                if s[i] == '+' or s[i] == '-' or s[i] == '*' or s[i] == '/':\n",
    "                    ops.append(s[last:i])\n",
    "                    ops.append(s[i:i+1])\n",
    "                    last = i+1\n",
    "            ops.append(s[last:])\n",
    "            return ops\n",
    "        ops = split()\n",
    "        \n",
    "        st = []\n",
    "        for op in ops:\n",
    "            if st:\n",
    "                if st[-1] == '*':\n",
    "                    op1 = st[-2]\n",
    "                    st.pop()\n",
    "                    st[-1] = int(op1) * int(op) \n",
    "                    continue\n",
    "\n",
    "                if st[-1] == '/':\n",
    "                    op1 = st[-2]\n",
    "                    st.pop()\n",
    "                    st[-1] = int(int(op1) / int(op))\n",
    "                    continue\n",
    "\n",
    "            st.append(op)\n",
    "        if len(st) < 2:\n",
    "            return int(st[0])\n",
    "        last_2 = int(st[0])\n",
    "        last = None\n",
    "        for op in st[1:]:\n",
    "            if last is None:\n",
    "                last = op\n",
    "                continue\n",
    "            if last == '+':\n",
    "                last_2 = last_2 + int(op)\n",
    "                last = None\n",
    "                continue\n",
    "            if last == '-':\n",
    "                last_2 = last_2 - int(op)\n",
    "                last = None\n",
    "                continue\n",
    "            \n",
    "        return last_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        \"\"\"巧妙利用sum()和0，效率较高\"\"\"\n",
    "        s = s.replace(' ','').replace('+',' + ').replace('-',' -').replace('*',' * ').replace('/',' / ')\n",
    "        val = s.split()\n",
    "        for i in range(len(val)):\n",
    "            if val[i]=='*':\n",
    "                val[i+1] = val[i-1]*int(val[i+1])\n",
    "                val[i],val[i-1] = 0,0\n",
    "            elif val[i]=='/':\n",
    "                val[i+1] = int(val[i-1]/int(val[i+1]))\n",
    "                val[i],val[i-1] = 0,0\n",
    "            elif val[i]=='+':\n",
    "                val[i] = 0\n",
    "            else:\n",
    "                val[i] = int(val[i])\n",
    "        return sum(val)\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "\n",
    "# 不使用栈的方法 使用正则 先计算全部的乘除 在计算加减法\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        先计算乘除 再计算加减\n",
    "        :param s:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        # 去除空格\n",
    "        s = re.sub(r\"([-+*/])\", r\" \\g<1> \", s.replace(\" \", \"\")).split()  # 正则标记出操作符\n",
    "        # 将运算符和数字分开存两个列表\n",
    "        (first, *nums), operas = s[::2], s[1::2]\n",
    "        ret = [int(first)]\n",
    "        for i, num_and_opera in enumerate(zip(nums, operas)):\n",
    "            num, opera = num_and_opera\n",
    "            if opera == \"*\":\n",
    "                ret[-1] *= int(num)\n",
    "            elif opera == \"/\":\n",
    "                if ret[-1] < 0:\n",
    "                    ret[-1] = -((-ret[-1]) // int(num))\n",
    "                else:\n",
    "                    ret[-1] //= int(num)\n",
    "            elif opera == \"-\":\n",
    "                # ret.append(\"+\")\n",
    "                ret.append(-int(num))\n",
    "            else:\n",
    "                # ret.append(opera)\n",
    "                ret.append(int(num))\n",
    "\n",
    "        print(ret)\n",
    "        return sum(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        stack = []\n",
    "        s += \"+\"\n",
    "        rst, sign = 0, 1\n",
    "        operators = {\"+\": 1, \"-\": -1, \"*\": 2, \"/\": 3}\n",
    "        for ch in s:\n",
    "            if ch == \" \":\n",
    "                continue\n",
    "            if ch.isdigit():\n",
    "                rst = rst * 10 + int(ch)\n",
    "            else:\n",
    "                if sign == 2 or sign == 3:\n",
    "                    cur_rst, cur_sign = stack.pop()\n",
    "                    rst = cur_rst * rst if sign == 2 else cur_rst // rst\n",
    "                    sign = cur_sign\n",
    "                stack.append((rst, sign))\n",
    "                rst = 0\n",
    "                sign = operators[ch]\n",
    "        \n",
    "        while stack:\n",
    "            cur_rst, cur_sign = stack.pop()\n",
    "            rst = cur_rst * cur_sign + rst\n",
    "    \n",
    "        return rst \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        nums = ('1', '2', '3', '4', '5', '6', '7', '8', '9', '0')\n",
    "        ops = ['+', '-', '*', '/']\n",
    "        s = s.replace(' ', '')\n",
    "        s = list(s)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        new_s = []\n",
    "\n",
    "        while j < len(s):\n",
    "            if s[j] in ops:\n",
    "                tmp = int(''.join(s[i:j]))\n",
    "                new_s.append(tmp)\n",
    "                new_s.append(s[j])\n",
    "                i = j+1\n",
    "                j = j+1\n",
    "            else:\n",
    "                j += 1\n",
    "        new_s.append(int(''.join(s[i:])))\n",
    "        print(new_s)\n",
    "        i = 1\n",
    "        \n",
    "        stack = list()\n",
    "        i = 0\n",
    "        while i < len(new_s):\n",
    "            c = new_s[i]\n",
    "            if c == '*':\n",
    "                tmp = stack.pop()\n",
    "                tmp *= new_s[i+1]\n",
    "                stack.append(tmp)\n",
    "                i += 2\n",
    "            elif c == '/':\n",
    "                tmp = stack.pop()\n",
    "                tmp = tmp // new_s[i+1]\n",
    "                stack.append(tmp)\n",
    "                i += 2\n",
    "            else:\n",
    "                stack.append(new_s[i])\n",
    "                i += 1\n",
    "        i = 1\n",
    "        res = stack[0]\n",
    "        while i < len(stack):\n",
    "            if stack[i] == '+':\n",
    "                res += stack[i+1]\n",
    "                i += 2\n",
    "            elif stack[i] == '-':\n",
    "                res -= stack[i+1]\n",
    "                i += 2\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s=s.replace(' ','')\n",
    "        p_add_del=re.compile('[\\+-]?\\d+')\n",
    "        p_mul_div=re.compile('(\\d+)[\\*/](\\d+)')\n",
    "        p_num=re.compile('\\d+')\n",
    "        sum_=0       \n",
    "        while re.search(p_mul_div,s) is not None:\n",
    "            mul_div=re.search(p_mul_div,s)\n",
    "            temp=s[mul_div.span()[0]:mul_div.span()[1]]\n",
    "            s=s.replace(temp,str(self.count(temp)),1)\n",
    "        add_del=p_add_del.findall(s)\n",
    "        for item in add_del:\n",
    "            if '-'in item:\n",
    "                sum_-=int(p_num.findall(item)[0])\n",
    "            else:\n",
    "                sum_+=int(p_num.findall(item)[0])\n",
    "        return int(sum_)\n",
    "    def count(self,s:str) ->int:\n",
    "        if '*' in s:\n",
    "            arr=s.split('*')\n",
    "            return int(arr[0])*int(arr[1])\n",
    "        if '/' in s:\n",
    "            arr=s.split('/')\n",
    "            return int(int(arr[0])/int(arr[1]))\n",
    "    \n",
    "\n",
    "        \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s=s.replace(' ','')\n",
    "        p_add_del=re.compile('[\\+-]?\\d+')\n",
    "        p_mul_div=re.compile('(\\d+)[\\*/](\\d+)')\n",
    "        p_num=re.compile('\\d+')\n",
    "        sum_=0\n",
    "        \n",
    "        while re.search(p_mul_div,s) is not None:\n",
    "            print(s)\n",
    "            mul_div=re.search(p_mul_div,s)\n",
    "            print(mul_div)\n",
    "            begin=mul_div.span()[0]\n",
    "            end=mul_div.span()[1]\n",
    "            temp=s[mul_div.span()[0]:mul_div.span()[1]]\n",
    "            print(temp)\n",
    "            s=s.replace(temp,str(self.count(temp)),1)\n",
    "\n",
    "        add_del=p_add_del.findall(s)\n",
    "        for item in add_del:\n",
    "            if '-'in item:\n",
    "                sum_-=int(p_num.findall(item)[0])\n",
    "            else:\n",
    "                sum_+=int(p_num.findall(item)[0])\n",
    "        print(sum_)\n",
    "        return int(sum_)\n",
    "\n",
    "    def count(self,s:str) ->int:\n",
    "        if '*' in s:\n",
    "            arr=s.split('*')\n",
    "            return int(arr[0])*int(arr[1])\n",
    "        if '/' in s:\n",
    "            arr=s.split('/')\n",
    "            # print(int(arr[0])/int(arr[1]))\n",
    "            return int(int(arr[0])/int(arr[1]))\n",
    "    \n",
    "\n",
    "        \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isfloat(self, str):\n",
    "        try:\n",
    "            float(str)\n",
    "            return True\n",
    "        except ValueError:\n",
    "            return False\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = s.replace(\" \", \"\")\n",
    "        s = s.replace(\"+\", \" + \")\n",
    "        s = s.replace(\"-\", \" - \")\n",
    "        s = s.replace(\"*\", \" * \")\n",
    "        s = s.replace(\"/\", \" / \")\n",
    "        \n",
    "        b = s.split(\" \")\n",
    "\n",
    "        stack = []\n",
    "        for i in range(len(b)): \n",
    "            if b[i] in [\"*\", \"/\"]:\n",
    "                temp = float(stack[-1]) * float(b[i+1]) if b[i] == \"*\" else int(float(stack[-1]) / float(b[i+1]))\n",
    "                stack.pop(-1)\n",
    "                stack.append(temp)\n",
    "                continue\n",
    "            if b[i-1] in [\"/\", \"*\", \"-\"]:\n",
    "                continue;\n",
    "            if b[i] in [\"-\"]:\n",
    "                temp = -float(b[i+1])\n",
    "                stack.append(temp)\n",
    "                continue\n",
    "            stack.append(float(b[i])) if self.isfloat(b[i]) else -1\n",
    "        \n",
    "        return(int(sum(stack)))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        \n",
    "        def zhongtohou(s):\n",
    "            hous = []\n",
    "            i = 0\n",
    "            fuhao = []\n",
    "            while i<len(s):\n",
    "                \n",
    "                if s[i].isdigit():\n",
    "                    nums = s[i]\n",
    "                    \n",
    "                    while i <len(s)-1:\n",
    "                        if s[i+1].isdigit():\n",
    "                            nums += s[i+1]\n",
    "                        else:\n",
    "                            break\n",
    "                        i =i+1\n",
    "                    \n",
    "                    hous.append(nums)\n",
    "                else:\n",
    "                    if s[i] == '+' or s[i] =='-':\n",
    "                        if fuhao == []:\n",
    "                            fuhao.append(s[i])\n",
    "                        else:\n",
    "                            while fuhao:\n",
    "                                hous += fuhao.pop()\n",
    "                            fuhao.append(s[i])\n",
    "                            \n",
    "                    if s[i] == '*' or s[i] == '/':\n",
    "                        while fuhao!=[] and (fuhao[-1] =='*' or fuhao[-1] =='/'):\n",
    "                            hous.append(fuhao.pop())\n",
    "                        \n",
    "                        fuhao.append(s[i])\n",
    "                i+=1\n",
    "            while fuhao:\n",
    "                 hous.append(fuhao.pop())\n",
    "            return hous\n",
    "        if s.strip(' ').isdigit():\n",
    "            return int(s)\n",
    "        houxu = zhongtohou(s)\n",
    "        result = 0\n",
    "        j =0\n",
    "        stack =[]\n",
    "        while j<len(houxu):\n",
    "            if houxu[j].isdigit():\n",
    "                stack.append(int(houxu[j]))\n",
    "            else:\n",
    "                if len(stack) ==1:\n",
    "                    a = stack.pop(-1)\n",
    "                    b = 0\n",
    "                else:\n",
    "                    a = stack.pop(-1)\n",
    "                    b = stack.pop(-1)\n",
    "                if houxu[j] == '+':\n",
    "                    c = b+a\n",
    "                if houxu[j] == '-':\n",
    "                    c = b-a\n",
    "                if houxu[j]=='*':\n",
    "                    c = b*a\n",
    "                if houxu[j] =='/':\n",
    "                    c = b//a\n",
    "                stack.append(c)\n",
    "            j+=1\n",
    "        result = stack[-1]\n",
    "\n",
    "        print(zhongtohou(s))     \n",
    "        return result       \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        def getpostexpre(s):\n",
    "            pri={'+':1,'-':1,'*':2,'/':2,'(': 0, ')': 0}\n",
    "            #中缀表达式转后缀表达式\n",
    "            output, stack=[],[]\n",
    "            num=0\n",
    "            for i in range(len(s)):\n",
    "                if s[i].isdigit():\n",
    "                    num=10*num+int(s[i])\n",
    "                elif s[i] in ['+','-','*','/']:\n",
    "                    output.append(str(num))\n",
    "                    num=0                    \n",
    "                    if stack and pri[s[i]]>pri[stack[-1]]:\n",
    "                        stack.append(s[i])\n",
    "                    else:\n",
    "                        while stack and pri[s[i]]<=pri[stack[-1]]:\n",
    "                            output.append(stack.pop())\n",
    "                        stack.append(s[i])\n",
    "                elif s[i]=='(':\n",
    "                    stack.append('(')\n",
    "                elif s[i]==')':\n",
    "                    while stack and stack[-1]!='(':\n",
    "                        output.append(stack.pop())\n",
    "                    stack.pop()\n",
    "            output.append(str(num))\n",
    "            while stack:\n",
    "                output.append(stack.pop())\n",
    "            return output                   \n",
    "        s=getpostexpre(s)\n",
    "        #print(s)\n",
    "        def cal(a,b,op):\n",
    "            if op=='+':return a+b\n",
    "            elif op=='-':return a-b\n",
    "            elif op=='*':return a*b\n",
    "            elif op=='/':return int(a/b)\n",
    "        nums=[]\n",
    "        for i in range(len(s)):\n",
    "           if s[i].isdigit():\n",
    "               nums.append(int(s[i]))\n",
    "           else:\n",
    "               b=nums.pop()\n",
    "               a=nums.pop()\n",
    "               x=cal(a,b,s[i])\n",
    "               nums.append(x)\n",
    "        return nums[0]\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def check_symbol(s):\n",
    "        if '*' in s:\n",
    "            return True\n",
    "        elif '/' in s:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def calculate(self, s: str) -> int:\n",
    "        # 去空格，并获取\n",
    "        _s_lst = s.replace(' ', '').replace('+', ' + ').replace('-', ' + -').replace('*', ' * ').replace('/', ' / ').split()\n",
    "        _int_lst = [int(n) if n not in ['+', '-', '*', '/'] else n for n in _s_lst]\n",
    "\n",
    "        while self.check_symbol(_int_lst):\n",
    "            for index, value in enumerate(_int_lst):\n",
    "                if value in ['*', '/']:\n",
    "                    if value == '/':\n",
    "                        symbol_flag = -1 if _int_lst[index - 1] < 0 else 1\n",
    "                    else:\n",
    "                        symbol_flag = 1\n",
    "\n",
    "                    _temp = _int_lst[index - 1] * _int_lst[index + 1] if value == '*' else abs(_int_lst[index - 1]) // _int_lst[index + 1]\n",
    "                    del _int_lst[index - 1]\n",
    "                    del _int_lst[index - 1]\n",
    "                    _int_lst[index - 1] = _temp * symbol_flag\n",
    "                    break\n",
    "\n",
    "        result_lst = [n for n in _int_lst if n not in ['-', '+']]\n",
    "        return sum(result_lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = s.replace(' ','').replace('+',' + ').replace('-',' -').replace('*',' * ').replace('/',' / ')\n",
    "        val = s.split()\n",
    "        print(val)\n",
    "        for i in range(len(val)):\n",
    "            if val[i]=='*':\n",
    "                val[i+1] = val[i-1]*int(val[i+1])\n",
    "                val[i],val[i-1] = 0,0\n",
    "            elif val[i]=='/':\n",
    "                val[i+1] = int(val[i-1]/int(val[i+1]))\n",
    "                val[i],val[i-1] = 0,0\n",
    "            elif val[i]=='+':\n",
    "                val[i] = 0\n",
    "            else:\n",
    "                val[i] = int(val[i])\n",
    "        print(val)\n",
    "        return sum(val)\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        l=list(s)\n",
    "        s=''\n",
    "        for i in l:\n",
    "            if i != ' ':\n",
    "                s=s+i\n",
    "        jiajian=[]\n",
    "        for i in range(0,len(s)):\n",
    "            if s[i]=='+' or s[i]=='-':\n",
    "                jiajian.append(i)\n",
    "        nums=[]\n",
    "        jj=list(tuple(jiajian))\n",
    "        jj.insert(0,-1)\n",
    "        jj.append(len(s))\n",
    "        results=[]\n",
    "        for i in range(0,len(jiajian)+1):\n",
    "            nums.append(s[jj[i]+1:jj[i+1]])\n",
    "        for num in nums:\n",
    "            chenchu=[]\n",
    "            for i in range(0,len(num)):\n",
    "                if num[i]=='*' or num[i]=='/':\n",
    "                    chenchu.append(i)\n",
    "            cc=list(tuple(chenchu))\n",
    "            cc.insert(0,-1)\n",
    "            cc.append(len(num))\n",
    "            numbers=[]\n",
    "            for i in range(0,len(chenchu)+1):\n",
    "                numbers.append(num[cc[i]+1:cc[i+1]])\n",
    "            result=int(numbers[0])\n",
    "            for i in range(0,len(chenchu)):\n",
    "                if num[chenchu[i]]=='*':\n",
    "                    result=result*int(numbers[i+1])\n",
    "                if num[chenchu[i]]=='/':\n",
    "                    result=result//int(numbers[i+1])\n",
    "            results.append(result)\n",
    "        re=results[0]\n",
    "        for i in range(0,len(jiajian)):\n",
    "            if s[jiajian[i]]=='+':\n",
    "                re=re+results[i+1]\n",
    "            if s[jiajian[i]]=='-':\n",
    "                re=re-results[i+1]\n",
    "        return re\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = s.replace(' ', '')\n",
    "        slist = []\n",
    "        idx, tmp = 0, ''\n",
    "\n",
    "        if s[idx] == '+' or s[idx] == '-':\n",
    "            tmp = s[idx]\n",
    "            idx += 1\n",
    "        \n",
    "        while idx < len(s):\n",
    "            if s[idx] == '+' or s[idx] == '-':\n",
    "                slist.append(tmp)\n",
    "                tmp = ''\n",
    "            tmp += s[idx]\n",
    "            idx += 1\n",
    "        slist.append(tmp)\n",
    "        print('first####', slist)\n",
    "        res = 0\n",
    "        for i in slist:\n",
    "            if ('*' not in i) and ('/' not in i):\n",
    "                res += int(i)\n",
    "            else:\n",
    "                num, idx, tmp, flag = 1, 0, '', 0\n",
    "                while idx < len(i):\n",
    "                    if i[idx] == '*':\n",
    "                        if flag == 0:\n",
    "                            num *= int(tmp)\n",
    "                        else:\n",
    "                            num = int(num/int(tmp))\n",
    "                        tmp, flag = '', 0\n",
    "                    \n",
    "                    elif i[idx] == '/':\n",
    "                        if flag == 0:\n",
    "                            num *= int(tmp)\n",
    "                        else:\n",
    "                            num = int(num/int(tmp))\n",
    "                        tmp, flag = '', 1\n",
    "                    \n",
    "                    else:\n",
    "                        tmp += i[idx]\n",
    "                    idx += 1\n",
    "                \n",
    "                if flag == 0:\n",
    "                    num *= int(tmp)\n",
    "                else:\n",
    "                    num = int(num/int(tmp))\n",
    "                res += num\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = re.sub('([*+-/])', r' \\1 ', s.replace(' ', '')).split()\n",
    "        (first, *nums), operates = s[:: 2], s[1:: 2]\n",
    "        queue, signs = [int(first)], []\n",
    "        for opr, num in zip(operates, nums):\n",
    "            if opr == '*':\n",
    "                queue[-1] *= int(num)\n",
    "            elif opr == '/':\n",
    "                queue[-1] //= int(num)\n",
    "            else:\n",
    "                queue.append(int(num))\n",
    "                signs.append(opr == '+' and 1 or -1)\n",
    "        return queue[0] + sum(i * j for i, j in zip(queue[1: ], signs))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = re.sub('([*+-/])', r' \\1 ', s.replace(' ', '')).split()\n",
    "        (first, *nums), operates = s[:: 2], s[1:: 2]\n",
    "        queue, signs = [int(first)], []\n",
    "        for opr, num in zip(operates, nums):\n",
    "            if opr == '*':\n",
    "                queue[-1] *= int(num)\n",
    "            elif opr == '/':\n",
    "                queue[-1] //= int(num)\n",
    "            else:\n",
    "                queue.append(int(num))\n",
    "                signs.append(opr == '+' and 1 or -1)\n",
    "        return queue[0] + sum(i * j for i, j in zip(queue[1: ], signs))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = re.sub('([*+-/])', r' \\1 ', s.replace(' ', '')).split()\n",
    "        (first, *nums), operates = s[:: 2], s[1:: 2]\n",
    "        queue, signs = [int(first)], []\n",
    "        for opr, num in zip(operates, nums):\n",
    "            if opr == '*':\n",
    "                queue[-1] *= int(num)\n",
    "            elif opr == '/':\n",
    "                queue[-1] //= int(num)\n",
    "            else:\n",
    "                queue.append(int(num))\n",
    "                signs.append(opr == '+' and 1 or -1)\n",
    "        return queue[0] + sum(i * j for i, j in zip(queue[1: ], signs))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        origin = s\n",
    "        text=origin.replace(' ', '')\n",
    "\n",
    "        while True:\n",
    "            match=re.findall(r'(\\d+)(\\/|\\*)(\\d+)', text)\n",
    "            if not match: break\n",
    "            match=match[0]\n",
    "            num1, sign, num2=match\n",
    "            if sign=='*': result=int(num1)*int(num2)\n",
    "            elif sign=='/': result=int(int(num1)/int(num2))\n",
    "            text=text.replace(''.join(list(match)), str(result), 1)\n",
    "\n",
    "        match=re.findall(r'([-+]?\\d+)', text)\n",
    "        result=sum([ int(i) for i in match ])\n",
    "\n",
    "        # print('# %s=%s'%(origin, result))\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = re.sub('([*+-/])', r' \\1 ', s.replace(' ', '')).split()\n",
    "        (first, *nums), operates = s[:: 2], s[1:: 2]\n",
    "        queue, signs = [int(first)], []\n",
    "        for opr, num in zip(operates, nums):\n",
    "            if opr == '*':\n",
    "                queue[-1] *= int(num)\n",
    "            elif opr == '/':\n",
    "                queue[-1] //= int(num)\n",
    "            else:\n",
    "                queue.append(int(num))\n",
    "                signs.append(opr == '+' and 1 or -1)\n",
    "        return queue[0] + sum(i * j for i, j in zip(queue[1: ], signs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        def isNumber(num: str) -> bool:\n",
    "            \"\"\"\n",
    "            判断是否是数字\n",
    "            :param num:\n",
    "            :return:\n",
    "            \"\"\"\n",
    "            return num.isdecimal()\n",
    "\n",
    "        s_list = list(s)\n",
    "        if '+' not in s_list and '-' not in s_list and '*' not in s_list and '/' not in s_list:\n",
    "            return int(s)\n",
    "        # 先去掉字符串中的空格\n",
    "        s = s.replace(' ', '')\n",
    "        s_stack = []\n",
    "        i = 0\n",
    "        # 先处理乘除\n",
    "        while i < len(s):\n",
    "            # 碰到加减和数字，压入栈\n",
    "            if s[i] == '+' or s[i] == '-':\n",
    "                s_stack.append(s[i])\n",
    "            elif isNumber(s[i]):\n",
    "                nums = s[i]\n",
    "                while i < len(s) - 1:\n",
    "                    if not isNumber(s[i + 1]):\n",
    "                        break\n",
    "                    else:\n",
    "                        nums += s[i+1]\n",
    "                        i += 1\n",
    "                s_stack.append(nums)\n",
    "            elif s[i] == '*' or s[i] == '/':\n",
    "                right = i + 1\n",
    "                s_left, s_right = '', ''\n",
    "                # 获取到 * / 左边的数字\n",
    "                while len(s_stack) != 0 and isNumber(s_stack[-1]):\n",
    "                    s_left += s_stack.pop()\n",
    "                # 获取到 * / 右边的数字\n",
    "                while right < len(s) and isNumber(s[right]):\n",
    "                    s_right += s[right]\n",
    "                    right += 1\n",
    "                # 计算出乘除的结果，压入栈中\n",
    "                if s[i] == '*':\n",
    "                    s_stack.append(str(int(s_left) * int(s_right)))\n",
    "                else:\n",
    "                    s_stack.append(str(int(s_left) // int(s_right)))\n",
    "                # 乘除右边的数字已经计算过了，所以要跳过\n",
    "                i = right\n",
    "                continue\n",
    "            i += 1\n",
    "        # 计算加减法\n",
    "        j = 0\n",
    "        while j < len(s_stack) - 1:\n",
    "            if '0' <= s_stack[j] <= '9':\n",
    "                j += 1\n",
    "                continue\n",
    "            elif s_stack[j] == '+':\n",
    "                s_stack[j + 1] = str(int(s_stack[j - 1]) + int(s_stack[j + 1]))\n",
    "                j += 1\n",
    "            elif s_stack[j] == '-':\n",
    "                s_stack[j + 1] = str(int(s_stack[j - 1]) - int(s_stack[j + 1]))\n",
    "                j += 1\n",
    "            j += 1\n",
    "        return int(s_stack[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        def isNumber(num: str) -> bool:\n",
    "            \"\"\"\n",
    "            判断是否是数字\n",
    "            :param num:\n",
    "            :return:\n",
    "            \"\"\"\n",
    "            return num.isdecimal()\n",
    "\n",
    "        s_list = list(s)\n",
    "        if '+' not in s_list and '-' not in s_list and '*' not in s_list and '/' not in s_list:\n",
    "            return int(s)\n",
    "        # 先去掉字符串中的空格\n",
    "        s = s.replace(' ', '')\n",
    "        s_stack = []\n",
    "        i = 0\n",
    "        # 先处理乘除\n",
    "        while i < len(s):\n",
    "            # 碰到加减和数字，压入栈\n",
    "            if s[i] == '+' or s[i] == '-':\n",
    "                s_stack.append(s[i])\n",
    "            elif isNumber(s[i]):\n",
    "                nums = s[i]\n",
    "                while i < len(s) - 1:\n",
    "                    if not isNumber(s[i + 1]):\n",
    "                        break\n",
    "                    else:\n",
    "                        nums += s[i+1]\n",
    "                        i += 1\n",
    "                s_stack.append(nums)\n",
    "            elif s[i] == '*' or s[i] == '/':\n",
    "                right = i + 1\n",
    "                s_left, s_right = '', ''\n",
    "                # 获取到 * / 左边的数字\n",
    "                while len(s_stack) != 0 and isNumber(s_stack[-1]):\n",
    "                    s_left += s_stack.pop()\n",
    "                # 获取到 * / 右边的数字\n",
    "                while right < len(s) and isNumber(s[right]):\n",
    "                    s_right += s[right]\n",
    "                    right += 1\n",
    "                # 计算出乘除的结果，压入栈中\n",
    "                if s[i] == '*':\n",
    "                    s_stack.append(str(int(s_left) * int(s_right)))\n",
    "                else:\n",
    "                    s_stack.append(str(int(s_left) // int(s_right)))\n",
    "                # 乘除右边的数字已经计算过了，所以要跳过\n",
    "                i = right\n",
    "                continue\n",
    "            i += 1\n",
    "        # 计算加减法\n",
    "        j = 0\n",
    "        while j < len(s_stack) - 1:\n",
    "            if '0' <= s_stack[j] <= '9':\n",
    "                j += 1\n",
    "                continue\n",
    "            elif s_stack[j] == '+':\n",
    "                s_stack[j + 1] = str(int(s_stack[j - 1]) + int(s_stack[j + 1]))\n",
    "                j += 1\n",
    "            elif s_stack[j] == '-':\n",
    "                s_stack[j + 1] = str(int(s_stack[j - 1]) - int(s_stack[j + 1]))\n",
    "                j += 1\n",
    "            j += 1\n",
    "        return int(s_stack[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = re.sub('([*+-/])', r' \\1 ', s.replace(' ', '')).split()\n",
    "        (first, *nums), operates = s[:: 2], s[1:: 2]\n",
    "        queue, signs = [int(first)], []\n",
    "        for opr, num in zip(operates, nums):\n",
    "            if opr == '*':\n",
    "                queue[-1] *= int(num)\n",
    "            elif opr == '/':\n",
    "                queue[-1] //= int(num)\n",
    "            else:\n",
    "                queue.append(int(num))\n",
    "                signs.append(opr == '+' and 1 or -1)\n",
    "        return queue[0] + sum(i * j for i, j in zip(queue[1: ], signs))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = re.sub('([*+-/])', r' \\1 ', s.replace(' ', '')).split()\n",
    "        (first, *nums), operates = s[:: 2], s[1:: 2]\n",
    "        queue, signs = [int(first)], []\n",
    "        for opr, num in zip(operates, nums):\n",
    "            if opr == '*':\n",
    "                queue[-1] *= int(num)\n",
    "            elif opr == '/':\n",
    "                queue[-1] //= int(num)\n",
    "            else:\n",
    "                queue.append(int(num))\n",
    "                signs.append(opr == '+' and 1 or -1)\n",
    "        return queue[0] + sum(i * j for i, j in zip(queue[1: ], signs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = re.sub('([+\\-*/])', r' \\1 ', s.replace(' ', '')).split()\n",
    "        (first, *nums), operates = s[:: 2], s[1:: 2]\n",
    "        queue, signs = [int(first)], []\n",
    "        for opr, num in zip(operates, nums):\n",
    "            if opr == '*':\n",
    "                queue[-1] *= int(num)\n",
    "            elif opr == '/':\n",
    "                queue[-1] //= int(num)\n",
    "            else:\n",
    "                queue.append(int(num))\n",
    "                signs.append(opr == '+' and 1 or -1)\n",
    "        return queue[0] + sum(i * j for i, j in zip(queue[1: ], signs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "\n",
    "# 不使用栈的方法 使用正则 先计算全部的乘除 在计算加减法\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        先计算乘除 再计算加减\n",
    "        :param s:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        # 去除空格\n",
    "        s = re.sub(r\"([+*/])\", r\" \\g<1> \", s.replace(\" \", \"\").replace(r\"-\", \"+-\")).split()  # 正则标记出操作符\n",
    "        print(s)\n",
    "\n",
    "        # 将运算符和数字分开存两个列表\n",
    "        ret = [int(s[0])]\n",
    "        for num_and_opera in zip(s[2::2], s[1::2]):\n",
    "            num, opera = num_and_opera\n",
    "            if opera == \"*\":\n",
    "                ret[-1] *= int(num)\n",
    "            elif opera == \"/\":\n",
    "                if ret[-1] < 0:\n",
    "                    ret[-1] = -((-ret[-1]) // int(num))\n",
    "                else:\n",
    "                    ret[-1] //= int(num)\n",
    "            else:\n",
    "                ret.append(int(num))\n",
    "        # print(ret)\n",
    "        return sum(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = s.replace(' ','')\n",
    "        def func(s,acc):\n",
    "            val = re.split(acc,s)\n",
    "            difs = ''.join(re.split('[^'+acc[1:3]+']',s))\n",
    "            if val[0]=='':val[:2] = ['-'+val[1]]\n",
    "            if len(val)==1:return s\n",
    "            ans = val[0]\n",
    "            for i in range(1,len(val)):\n",
    "                if difs[i-1]=='*':\n",
    "                    ans = str(int(ans)*int(val[i]))\n",
    "                elif difs[i-1]=='/':\n",
    "                    ans = str(int(ans)//int(val[i]))\n",
    "                elif difs[i-1]=='+':\n",
    "                    ans = str(int(ans)+int(val[i]))\n",
    "                else:\n",
    "                    ans = str(int(ans)-int(val[i]))\n",
    "            return ans\n",
    "        nums = re.split('[+-]',s)\n",
    "        diff = ''.join(re.split('[^+-]',s))\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = func(nums[i],'[*/]')\n",
    "        for i in range(len(diff)):\n",
    "            nums[i]+=diff[i]\n",
    "        return int(func(''.join(nums),'[+-]'))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = s.replace(' ','')\n",
    "        def func(s,acc):\n",
    "            val = re.split(acc,s)\n",
    "            difs = ''.join(re.split('[^'+acc[1:3]+']',s))\n",
    "            if len(val)==1:return s\n",
    "            ans = val[0]\n",
    "            for i in range(1,len(val)):\n",
    "                if difs[i-1]=='*':\n",
    "                    ans = str(int(ans)*int(val[i]))\n",
    "                elif difs[i-1]=='/':\n",
    "                    ans = str(int(ans)//int(val[i]))\n",
    "                elif difs[i-1]=='+':\n",
    "                    ans = str(int(ans)+int(val[i]))\n",
    "                else:\n",
    "                    ans = str(int(ans)-int(val[i]))\n",
    "            return ans\n",
    "        nums = re.split('[+-]',s)\n",
    "        diff = ''.join(re.split('[^+-]',s))\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = func(nums[i],'[*/]')\n",
    "        for i in range(len(diff)):\n",
    "            nums[i]+=diff[i]\n",
    "        return int(func(''.join(nums),'[+-]'))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, s: str) -> int:\n",
    "        s = s.replace(' ','')\n",
    "        def func(s,acc):\n",
    "            val = re.split(acc,s)\n",
    "            difs = ''.join(re.split('[^'+acc[1:3]+']',s))\n",
    "            # if val[0]=='':\n",
    "            #     val[:2] = ['-'+val[1]]\n",
    "            if len(val)==1:return s\n",
    "            ans = val[0]\n",
    "            for i in range(1,len(val)):\n",
    "                if difs[i-1]=='*':\n",
    "                    ans = str(int(ans)*int(val[i]))\n",
    "                elif difs[i-1]=='/':\n",
    "                    ans = str(int(ans)//int(val[i]))\n",
    "                elif difs[i-1]=='+':\n",
    "                    ans = str(int(ans)+int(val[i]))\n",
    "                else:\n",
    "                    ans = str(int(ans)-int(val[i]))\n",
    "            return ans\n",
    "        nums = re.split('[+-]',s)\n",
    "        diff = ''.join(re.split('[^+-]',s))\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = func(nums[i],'[*/]')\n",
    "        for i in range(len(diff)):\n",
    "            nums[i]+=diff[i]\n",
    "        return int(func(''.join(nums),'[+-]'))\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
